Parameterized graph cleaning problems

DOI10.1016/j.dam.2009.06.022zbMath1209.05248OpenAlexW2147058408MaRDI QIDQ967382

Ildikó Schlotter, Dániel Marx

Publication date: 28 April 2010

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2009.06.022

zbMATH Keywords

graph algorithmfixed-parameter tractabilityinduced subgraph isomorphism

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (3)

Cleaning interval graphs ⋮ Approximation and tidying -- a problem kernel for \(s\)-plex cluster vertex deletion ⋮ On retracts, absolute retracts, and foldings in cographs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth
• On the complexity of finding iso- and other morphisms for partial \(k\)- trees
• Subgraph isomorphism for biconnected outerplanar graphs in cubic time
• Parametrized complexity theory.
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
• Obtaining a Planar Graph by Vertex Deletion
• Understanding the Complexity of Induced Subgraph Isomorphisms
• A Cubic Kernel for Feedback Vertex Set
• Efficient Planarity Testing
• Subtree Isomorphism in O(n5/2)
• ON DISJOINT CYCLES
• Subgraph Isomorphism in Planar Graphs and Related Problems
• Dividing a Graph into Triconnected Components
• Fast FPT-Algorithms for Cleaning Grids

This page was built for publication: Parameterized graph cleaning problems