Parameterized complexity of finding connected induced subgraphs

DOI10.1016/J.TCS.2015.05.020zbMath1332.68067OpenAlexW399388665MaRDI QIDQ897959

Junjie Ye, Leizhen Cai

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

hereditary propertiesparameterized complexityconnected induced subgraphs

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding odd cycle transversals.
• Chordal deletion is fixed-parameter tractable
• The parameterized complexity of the induced matching problem
• The node-deletion problem for hereditary properties is NP-complete
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Parameterized complexity of finding subgraphs with hereditary properties.
• Parameterized complexity of the induced subgraph problem in directed graphs
• Obtaining a planar graph by vertex deletion
• Moore graphs and beyond: a survey of the degree/diameter problem
• Dual Connectedness of Edge-Bicolored Graphs and Beyond
• Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
• ON DISJOINT CYCLES
• An FPT Algorithm for Tree Deletion Set
• Parameterized Complexity of Connected Induced Subgraph Problems
• Interval Deletion is Fixed-Parameter Tractable

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