Necessary condition for path partitioning constraints
(2007) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. 4th International Conference, CPAIOR 2007 — Location: Brussels, Belgium (23.May.2007)
Files
No attached file found for this publication.
Details
- Authors
- Abstract
- Given a directed graph G, the K node-disjoint paths problem consists in finding a partition of G into K node-disjoint paths, such that each path ends up in a given subset of nodes in G. This article provides a necessary condition for the K node-disjoint paths problem which combines (1) the structure of the reduced graph associated with G, (2) the structure of each strongly connected component of G with respect to dominance relation between nodes, and (3) the way the nodes of two strongly connected components are inter-connected. This necessary condition is next used to deal with a path partitioning constraint.
- Affiliations
Citations
Beldiceanu, N., & Lorca, X. (2007). Necessary condition for path partitioning constraints. In Van Hentenryck, P.; Wolsey, L.; (ed.), Integration of AI and OR Techniques in Constraint Programming forCombinatorial Optimization Problems. Proceedings 4th InternationalConference, CPAIOR 2007 (p. p. 141-154). Springer-verlag. https://hdl.handle.net/2078.5/230964