On generalizations of the shadow independent set problem

DOI10.1016/J.DISC.2005.11.084MaRDI QIDQ878644zbMATH OpenOpenAlexFDO

Authors 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

directed acyclic graphdynamic programmingforestfixed parameter tractability(relational) shadow patternshadow independent set

Mathematics Subject Classification ID

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

Recommendations

• Improving a fixed parameter tractability time bound for the shadow problem
• Parameterized algorithms for the independent set problem in some hereditary graph classes
• The maximum independent set problem in subclasses of \(S_{i, j, k}\)-free graphs
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Independent sets in graphs without subtrees with many leaves

Cites work

• scientific article; zbMATH DE number 125608 (Why is no real title available?)
• scientific article; zbMATH DE number 833906 (Why is no real title available?)
• An algorithm for the class of pure implicational formulas
• Improving a fixed parameter tractability time bound for the shadow problem
• The complexity of the falsifiability problem for pure implicational formulas

Cited in

(2)

• On maximal shadows of members in left-compressed sets
• Improving a fixed parameter tractability time bound for the shadow problem

This page was built for publication: On generalizations of the shadow independent set problem

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