Parameterized complexity of finding connected induced subgraphs
DOI10.1016/J.TCS.2015.05.020zbMATH Open1332.68067OpenAlexW399388665MaRDI QIDQ897959FDOQ897959
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
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
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)
Cites Work
- Title not available (Why is that?)
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Finding odd cycle transversals.
- The node-deletion problem for hereditary properties is NP-complete
- Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
- Title not available (Why is that?)
- ON DISJOINT CYCLES
- Moore graphs and beyond: a survey of the degree/diameter problem
- Title not available (Why is that?)
- Chordal deletion is fixed-parameter tractable
- The parameterized complexity of the induced matching problem
- Parameterized complexity of finding subgraphs with hereditary properties.
- Obtaining a planar graph by vertex deletion
- Parameterized complexity of connected induced subgraph problems
- Dual connectedness of edge-bicolored graphs and beyond
- Parameterized complexity of the induced subgraph problem in directed graphs
- An FPT algorithm for tree deletion set
- Interval deletion is fixed-parameter tractable
Cited In (8)
- Parameterized complexity of connected even/odd subgraph problems
- Parameterized complexity of connected induced subgraph problems
- Parameterized complexity of finding subgraphs with hereditary properties.
- The parameterized complexity of \(k\)-edge induced subgraphs
- The Parameterized Complexity of k-Edge Induced Subgraphs
- Title not available (Why is that?)
- Finding connected secluded subgraphs
- 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)
