Parameterized Graph Cleaning Problems

DOI10.1007/978-3-540-92248-3_26zbMath1202.05088OpenAlexW2151639961MaRDI QIDQ5302063

Ildikó Schlotter, Dániel Marx

Publication date: 20 January 2009

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.709.7344

zbMATH Keywords

fixed parameter tractabilityinduced subgraph isomorphism problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth
• Subgraph isomorphism for biconnected outerplanar graphs in cubic time
• Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
• Obtaining a Planar Graph by Vertex Deletion
• 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