Middendorf, Matthias and Pfeiffer, Frank (1990) The Paths-Selection-Problem.
Published In: Polyhedral combinatorics : proceedings of a DIMACS Workshop ; June 12 - 16, 1989, DIMACS series in discrete mathematics and theoretical computer science. 1 1990, pp. 179-187.

Abstract

Let P and Q be two disjoint finite length paths with corresponding integer capacity functions c(sub P) and c(sub Q), and let S = {(s((sup P), (sub i)),s((sup Q), (sub i))): i in I} be a system of pairs of paths, the first a subpath of P and the second a subpath of Q. The path selection problem is ''Does there exists a choice-function h which respects the given capacities?'' (i.e., a function h: I -> {0,1} with |{i in h sup(-1)[0] : e in s((sup P), (sub i))}|<= c(sub P) (e) for e in E(P) and | {i in h sup(-1)[1] : e in s((sup Q), (sub i))}|<= c(sub Q) (e) for e in E(Q)). The general paths-selection problem is shown to be NP-complete. A special case of the problem is shown to be equivalent to finding the independence number of an interval graph. The complexity of other related problems, such as the ''multiterminal grid-joining problem'' and the 'Èulerian disjoint-paths problem'' are considered, and shown to be NP-complete as well.

Actions:

Full text not available from this repository.

Editorial actions:	View Item (Login required)