General

Authors

Search


Committee login



 
 

 


 

 

Forthcoming

Small thumbnail

Secure Connected Objects

Small thumbnail

Banach, Fréchet, Hilbert and Neumann Spaces

Analysis for PDEs Set Volume 1

Small thumbnail

Semi-Markov Migration Models for Credit Risk

Stochastic Models for Insurance Set Volume 1

Small thumbnail

Human Exposure to Electromagnetic Fields

From Extremely Low Frequency (ELF) to Radio Frequency

Small thumbnail

Enterprise Interoperability

INTEROP-PGSO Vision

Small thumbnail

Data Treatment in Environmental Sciences

Multivaried Approach

Small thumbnail

From Pinch Methodology to Pinch-Exergy Integration of Flexible Systems

Thermodynamics Energy, Environment, Economy Set

Small thumbnail

Exterior Algebras

Elementary Tribute to Grassmann's Ideas

Small thumbnail

Nonlinear Theory of Elastic Plates

Small thumbnail

Cognitive Approach to Natural Language Processing

Small thumbnail

Tree-based Graph Partitioning Constraint

Xavier Lorca, Ecole des Mines de Nantes, France

ISBN: 9781848213036

Publication Date: June 2011   Hardback   256 pp.

96.00 USD


Add to cart

eBooks


Ebook Ebook

Description

Combinatorial problems based on graph partitioning enable us to mathematically represent and model many practical applications. Mission planning and the routing problems occurring in logistics perfectly illustrate two such examples. Nevertheless, these problems 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 theoretical problems like the Hamiltonian path problem, or K-node disjoint path problems. Indeed, they usually combine the graph partitioning problem with several restrictions related to the topology of nodes and arcs. The diversity of implied constraints in real-life applications is a practical limit to the resolution of such problems by approaches considering the partitioning problem independently from each additional restriction.
This book focuses on constraint satisfaction problems related to tree partitioning problems enriched by several additional constraints that restrict the possible partitions topology. On the one hand, this title focuses on the structural properties of tree partitioning constraints. On the other hand, it is dedicated to the interactions between the tree partitioning problem and classical restrictions (such as precedence relations or incomparability relations between nodes) involved in practical applications.
Precisely, Tree-based Graph Partitioning Constraint shows how to globally take into account several restrictions within one single tree partitioning constraint. Another interesting aspect of this book is related to the implementation of such a constraint. In the context of graph-based global constraints, the book illustrates how a fully dynamic management of data structures makes the runtime of filtering algorithms independent of the graph density.

Contents

Part 1. Constraint Programming and Foundations of Graph Theory
1. Introduction to Constraint Programming.
2. Graph Theory and Constraint Programming.
3. Tree Graph Partitioning.
Part 2. Characterization of Tree-based Graph Partitioning Constraints
4. Tree Constraints in Undirected Graphs.
5. Tree Constraints in Directed Graphs.
6. Additional Constraints Linked to Graph Partitioning.
7.The Case of Disjoint Paths.
8. Implementation of a Tree Constraint.
Part 3. Implementation: Task Planning
9. First Model in Constraint Programming.
10. Advanced Model in Constraint Programming.
11. Conclusion.
12. Perspectives and Criticisms.

About the Authors

Xavier Lorca is Associate Professor of Computer Science at the Ecole des Mines de Nantes in France and manages its research activities on Constraint Programming at the CNRS research lab LINA. Prior to his current position, he obtained his PhD in Constraint Programming from the University of Nantes in 2007.

Downloads

DownloadTable of Contents - PDF File - 43 Kb

Related Titles



































0.07397 s.