The Case of Disjoint Paths
Xavier Lorca · 2011
In the context of partitioning constraints, the aim of this chapter is to demonstrate how the combination of reasoning on flow and a reasoning on the dominance relation between the graph vertices provides a necessary condition for the path partitioning constraint. This constraint has exactly the same arguments as the tree constraint. The chapter presents an approach based on flows in the context of directed graphs that do not have a circuit (directed acyclic graph, DAG). Afterwards, it shows how to extend this model to any graph, by considering the reduced graph and linked with a directed graph. Finally, the chapter demonstrates how to use a part of the flow model linked to the problem of K vertex-disjoint paths with the aim of improving the filtering linked to the path partitioning constraint. Controlled Vocabulary Terms bayesian network; graphical model; partitioning