scientific article; zbMATH DE number 2044949

MaRDI QIDQ4448769zbMATHFDO

Authors Antonio Puricella, Iain Stewart

Publication date 18 February 2004

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

Mathematics Subject Classification ID

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

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)

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

This page was built for publication:

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