Cleaning interval graphs

DOI10.1007/s00453-011-9588-0zbMath1259.68082arXiv1003.1260OpenAlexW1505464468MaRDI QIDQ1939654

Ildikó Schlotter, Dániel Marx

Publication date: 5 March 2013

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1003.1260

zbMATH Keywords

interval graphsparameterized complexityinduced subgraph isomorphism

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) 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)

Related Items (8)

FO model checking on geometric graphs ⋮ Twin-width II: small classes ⋮ On the complexity of various parameterizations of common induced subgraph isomorphism ⋮ Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs ⋮ Subgraph isomorphism in graph classes ⋮ Induced subgraph isomorphism on proper interval and bipartite permutation graphs ⋮ On retracts, absolute retracts, and foldings in cographs ⋮ Unnamed Item

Cites Work

• Unnamed Item
• On an algorithm of Zemlyachenko for subtree isomorphism
• Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth
• Parameterized graph cleaning problems
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Subgraph isomorphism for biconnected outerplanar graphs in cubic time
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
• Linear Time Automorphism Algorithms for Trees, Interval Graphs, and Planar Graphs
• On testing isomorphism of permutation graphs
• Subtree Isomorphism in O(n5/2)
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• Subgraph Isomorphism in Planar Graphs and Related Problems
• Fast FPT-Algorithms for Cleaning Grids
• A Characterization of Comparability Graphs and of Interval Graphs

This page was built for publication: Cleaning interval graphs