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

DOI10.1007/3-540-45477-2_28MaRDI QIDQ4448769zbMATH OpenFDO

Authors Antonio Puricella, Iain Stewart

Publication date 18 February 2004

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2204/22040306.htm

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• NP-completeness results concerning greedy and super greedy linear extensions
• Greedy algorithms, H-colourings and a complexity-theoretic dichotomy.
• scientific article; zbMATH DE number 4047154
• On the computational complexity of ordered subgraph recognition
• The lexicographically first maximal subgraph problems:P-completeness andNC algorithms

Cited in

(5)

• NP-completeness results concerning greedy and super greedy linear extensions
• Greedy algorithms, H-colourings and a complexity-theoretic dichotomy.
• Dichotomies for classes of homomorphism problems involving unary functions
• Greedy-type resistance of combinatorial problems
• Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties

This page was built for publication: A generic greedy algorithm, partially-ordered graphs and NP-completeness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4448769)