Parameterized graph cleaning problems
From MaRDI portal
Publication:967382
DOI10.1016/j.dam.2009.06.022zbMath1209.05248OpenAlexW2147058408MaRDI QIDQ967382
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
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