On generalizations of the shadow independent set problem

DOI10.1016/J.DISC.2005.11.084zbMATH Open1178.68383OpenAlexW2007081414MaRDI QIDQ878644FDOQ878644

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

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

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)

Cites Work

• Title not available (Why is that?)
• Improving a fixed parameter tractability time bound for the shadow problem
• An algorithm for the class of pure implicational formulas
• Title not available (Why is that?)
• 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)