Parameterized complexity of finding connected induced subgraphs

DOI10.1016/J.TCS.2015.05.020MaRDI QIDQ897959zbMATH OpenOpenAlexFDO

Authors Leizhen Cai, Junjie Ye

Publication date 8 December 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2015.05.020

zbMATH Keywords

parameterized complexityhereditary propertiesconnected induced subgraphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Structural characterization of families of graphs (05C75)

Recommendations

• Parameterized complexity of connected induced subgraph problems
• Parameterized complexity of finding regular induced subgraphs
• Parameterized complexity of the induced subgraph problem in directed graphs
• The parameterized complexity of k-edge induced subgraphs
• The Parameterized Complexity of k-Edge Induced Subgraphs
• Parameterized complexity of connected even/odd subgraph problems
• Parameterized complexity of connected even/odd subgraph problems
• Parameterized computational complexity of finding small-diameter subgraphs
• Parameterized complexity of finding small degree-constrained subgraphs
• The parameterised complexity of counting connected subgraphs and graph motifs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1261820 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• An FPT algorithm for tree deletion set
• Chordal deletion is fixed-parameter tractable
• Dual connectedness of edge-bicolored graphs and beyond
• Finding odd cycle transversals.
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Interval deletion is fixed-parameter tractable
• Moore graphs and beyond: a survey of the degree/diameter problem
• ON DISJOINT CYCLES
• Obtaining a planar graph by vertex deletion
• Parameterized complexity of connected induced subgraph problems
• Parameterized complexity of finding subgraphs with hereditary properties.
• Parameterized complexity of the induced subgraph problem in directed graphs
• Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
• The node-deletion problem for hereditary properties is NP-complete
• The parameterized complexity of the induced matching problem

Cited in

(8)

• Finding connected secluded subgraphs
• The Parameterized Complexity of k-Edge Induced Subgraphs
• Parameterized complexity of connected even/odd subgraph problems
• scientific article; zbMATH DE number 1696630 (Why is no real title available?)
• The parameterized complexity of \(k\)-edge induced subgraphs
• Parameterized complexity of connected induced subgraph problems
• Parameterized complexity of finding subgraphs with hereditary properties.
• Finding connected secluded subgraphs

This page was built for publication: Parameterized complexity of finding connected induced subgraphs

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