Tree-Based Graph Partitioning Constraint

By Xavier Lorca

Combinatorial problems based on graph partitioning enable us tomathematically represent and model many practical applications.Mission planning and the routing problems occurring in logisticsperfectly illustrate two such examples. Nevertheless, theseproblems are not based on the same partitioning pattern: generally, patterns like cycles, paths, or trees are distinguished. Moreover, the practical applications are often not limited to theoreticalproblems like the Hamiltonian path problem, or K-node disjoint pathproblems. Indeed, they usually combine the graph partitioningproblem with several restrictions related to the topology of nodesand arcs. The diversity of implied constraints in real-lifeapplications is a practical limit to the resolution of suchproblems by approaches considering the partitioning problemindependently from each additional restriction.
This book focuses on constraint satisfaction problems related totree partitioning problems enriched by several additionalconstraints that restrict the possible partitions topology. On theone hand, this title focuses on the structural properties of treepartitioning constraints. On the other hand, it is dedicated to theinteractions between the tree partitioning problem and classicalrestrictions (such as precedence relations or incomparabilityrelations between nodes) involved in practical applications.
Precisely, Tree-based Graph Partitioning Constraint shows how toglobally take into account several restrictions within one singletree partitioning constraint. Another interesting aspect of thisbook is related to the implementation of such a constraint. In thecontext of graph-based global constraints, the book illustrates howa fully dynamic management of data structures makes the runtime offiltering algorithms independent of the graph density.

• Format: Hardcover
• Language: English
• ISBN: 1848213034
• ISBN13: 9781848213036
• Release Date: August 2011
• Publisher: Wiley-Iste
• Length: 240 Pages
• Weight: 1.25 lbs.
• Dimensions: 1.0" x 6.2" x 9.2"