A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs
From MaRDI portal
Publication:3512472
DOI10.1007/978-3-540-69903-3_32zbMath1155.05339MaRDI QIDQ3512472
Francisco J. Soulignac, Min Chih Lin, Jayme Luiz Szwarcfiter
Publication date: 15 July 2008
Published in: Algorithm Theory – SWAT 2008 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-69903-3_32
05C85: Graph algorithms (graph-theoretic aspects)
05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
Related Items
Circle graph isomorphism in almost linear time, On the isomorphism problem for Helly circular-arc graphs, Solving the canonical representation and star system problems for proper circular-arc graphs in logspace, Circular-arc hypergraphs: rigidity via connectedness, The clique operator on circular-arc graphs, Normal Helly circular-arc graphs and its subclasses, Revising Johnson's table for the 21st century, Complexity-separating graph classes for vertex, edge and total colouring, Fully dynamic recognition of proper circular-arc graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Lexicographically least circular substrings
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Efficient graph representations
- Linear-time recognition of circular-arc graphs
- Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
- Algorithmic graph theory and perfect graphs
- Proper Helly Circular-Arc Graphs
- Certifying Algorithms for Recognizing Proper Circular-Arc Graphs and Unit Circular-Arc Graphs
- Unit Circular-Arc Graph Representations and Feasible Circulations
- An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
- Fast canonization of circular strings
- A Linear Time Algorithm for Deciding Interval Graph Isomorphism
- Graph Classes: A Survey
- $O(M\cdot N)$ Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
- Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
- A Linear Algorithm for Maximum Weight Cliques in Proper Circular Arc Graphs
- A Simpler Linear-Time Recognition of Circular-Arc Graphs
