scientific article; zbMATH DE number 2044949

zbMATH Open1042.68644MaRDI QIDQ4448769FDOQ4448769

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

Title of this publication is not available (Why is that?)

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

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)

Cited In (5)

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

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)