On generalizations of the shadow independent set problem

DOI10.1016/j.disc.2005.11.084zbMath1178.68383OpenAlexW2007081414MaRDI QIDQ878644

Stefan Porschen

Publication date: 26 April 2007

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2005.11.084

zbMATH Keywords

dynamic programmingdirected acyclic graphfixed parameter tractabilityforest(relational) shadow patternshadow independent set

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• Improving a fixed parameter tractability time bound for the shadow problem
• An algorithm for the class of pure implicational formulas
• The complexity of the falsifiability problem for pure implicational formulas