Next:
Introduction
Up:
T. Zurek: Optimisation of
Previous:
Temporal-Specific Join Optimisation Issues
The Interval Partitioning Problem
Introduction
Preliminaries
Problem Definition
Definition
:
Interval Partitioning - IP
Proof:
Search Space
Proof:
Proof:
Proof:
Optimal Partitioning
Algorithm for Optimal Partitioning
Algorithm
IP-opt
Example
Correctness
Proof:
Alternative: Reducing IP to a Graph-Theoretic Problem
Sequential Graph Partitioning
Definition
:
Sequential Graph Partitioning - SGP
Reducing IP to SGP
Definition
:
Example
Correctness
Proof:
Proof of (5.15)
Proof of (5.16)
Optimal Solution for SGP
Algorithm
SGP-opt
Example
Run-Time Complexity Analysis
Proof
Thomas Zurek
