The Paths-Selection-Problem
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.
Item Type: | Proceedings article |
---|---|
Citations: | 0 (Google Scholar) | |
Uncontrolled Keywords: | Euler paths general paths-selection problem grids NP-completeness path selection problem |
Subjects: |
|
Divisions: | Mathematical Institute |
Related URLs: |
ZAIK Number: | zpr91-103 |
---|---|
Depositing User: | Archive Admin |
Date Deposited: | 02 Apr 2001 00:00 |
Last Modified: | 09 Jan 2012 11:51 |
URI: | http://e-archive.informatik.uni-koeln.de/id/eprint/103 |