A generic greedy algorithm, partially-ordered graphs and NP-completeness

Puricella, A.; Stewart, I.A.

doi:10.1007/3-540-45477-2_28

A generic greedy algorithm, partially-ordered graphs and NP-completeness

Puricella, A.; Stewart, I.A.

Authors

A. Puricella

Professor Iain Stewart i.a.stewart@durham.ac.uk
Professor

Contributors

A. Brandstaedt
Editor

V.B. Le
Editor

Abstract

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.

Citation

Puricella, A., & Stewart, I. (2001). A generic greedy algorithm, partially-ordered graphs and NP-completeness. In A. Brandstaedt, & V. Le (Eds.), Graph-theoretic concepts in computer science : 27th International Workshop, WG 2001, 14-16 June 2001, Boltenhagen, Germany ; proceedings (306-316). https://doi.org/10.1007/3-540-45477-2_28

Conference Name	27th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2001)
Conference Location	Rostock, Germany
Start Date	Jun 14, 2001
End Date	Jun 16, 2001
Publication Date	Oct 2, 2001
Deposit Date	Jul 2, 2009
Publicly Available Date	Aug 25, 2009
Pages	306-316
Series Title	Lecture notes in computer science
Series Number	2204
Series ISSN	0302-9743,1611-3349
Book Title	Graph-theoretic concepts in computer science : 27th International Workshop, WG 2001, 14-16 June 2001, Boltenhagen, Germany ; proceedings.
ISBN	9783540427070
DOI	https://doi.org/10.1007/3-540-45477-2_28
Keywords	Greedy algorithms, NP-completeness, Hereditary properties.
Public URL	https://durham-repository.worktribe.com/output/1695306