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:||PDF - Accepted Version (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|
|Record Created:||02 Jul 2009 14:50|
|Last Modified:||31 Mar 2015 12:39|
|Social bookmarking:||Export: EndNote, Zotero | BibTex|
|Usage statistics||Look up in GoogleScholar | Find in a UK Library|