Puricella, A. and Stewart, I. A. (2001) 'A generic greedy algorithm, partially-ordered graphs and NP-completeness.', in Graph-theoretic concepts in computer science : 27th International Workshop, WG 2001, 14-16 June 2001, Boltenhagen, Germany ; proceedings. Berlin: Springer, pp. 306-316. Lecture notes in computer science. (2204).
Let π be any fixed polynomial-time testable, non-trivial, hereditary property of graphs. Suppose that the vertices of a graph G are not necessarily linearly ordered but partially ordered, where we think of this partial order as a collection of (possibly exponentially many) linear orders in the natural way. We prove that the problem of deciding whether a lexicographically first maximal subgraph of G satisfying π, with respect to one of these linear orders, contains a specified vertex is NP-complete.
|Item Type:||Book chapter|
|Keywords:||Greedy algorithms, NP-completeness, Hereditary properties.|
|Full text:||(AM) Accepted Manuscript|
Download PDF (225Kb)
|Publisher Web site:||http://dx.doi.org/10.1007/3-540-45477-2_28|
|Publisher statement:||The final publication is available at Springer via http://dx.doi.org/10.1007/3-540-45477-2_28|
|Date accepted:||No date available|
|Date deposited:||25 August 2009|
|Date of first online publication:||January 2001|
|Date first made open access:||No date available|
Save or Share this output
|Look up in GoogleScholar|