The PathsSelectionProblem
Middendorf, Matthias and Pfeiffer, Frank
(1990)
The PathsSelectionProblem.
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. 179187.
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 choicefunction 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 pathsselection problem is shown to be NPcomplete. 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 gridjoining problem'' and the 'Èulerian disjointpaths problem'' are considered, and shown to be NPcomplete as well.
Item Type:  Proceedings article 

Citations:  0 (Google Scholar)  
Uncontrolled Keywords:  Euler paths general pathsselection problem grids NPcompleteness path selection problem 
Subjects: 

Divisions:  Mathematical Institute 
Related URLs: 
ZAIK Number:  zpr91103 

Depositing User:  Archive Admin 
Date Deposited:  02 Apr 2001 00:00 
Last Modified:  09 Jan 2012 11:51 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/103 