Parameterized complexity of finding subgraphs with hereditary properties

DOI10.1007/3-540-44968-X_14MaRDI QIDQ2766822zbMATH OpenFDO

Authors Subhash Khot, Venkatesh Raman

Publication date 22 July 2002

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-44968-X_14

Mathematics Subject Classification ID

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

Recommendations

• Parameterized complexity of finding subgraphs with hereditary properties.
• Parameterized complexity of connected induced subgraph problems
• Parameterized complexity of finding connected induced subgraphs
• Parameterized complexity of the induced subgraph problem in directed graphs
• Parameterized complexity of the maximum independent set problem and the speed of hereditary properties

Cited in

(15)

• Parameterized complexity of finding subgraphs with hereditary properties.
• Revising Johnson's table for the 21st century
• Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes
• Parameterized complexity of the induced subgraph problem in directed graphs
• Additive approximation for edge-deletion problems
• Kernel lower bounds using co-nondeterminism: finding induced hereditary subgraphs
• Parameterized complexity: the main ideas and connections to practical computing
• Parameterized complexity of the maximum independent set problem and the speed of hereditary properties
• Kernel lower bounds using co-nondeterminism: finding induced hereditary subgraphs
• The complexity of minor-ancestral graph properties with forbidden pairs
• The parameterized complexity of finding point sets with hereditary properties
• From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
• Parameterized complexity of connected induced subgraph problems
• Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels
• scientific article; zbMATH DE number 7651174 (Why is no real title available?)

This page was built for publication: Parameterized complexity of finding subgraphs with hereditary properties

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