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.05339OpenAlexW1585739861MaRDI 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
Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items (9)
Solving the canonical representation and star system problems for proper circular-arc graphs in logspace ⋮ Complexity-separating graph classes for vertex, edge and total colouring ⋮ Circle graph isomorphism in almost linear time ⋮ Normal Helly circular-arc graphs and its subclasses ⋮ Circular-arc hypergraphs: rigidity via connectedness ⋮ The clique operator on circular-arc graphs ⋮ Revising Johnson's table for the 21st century ⋮ Fully dynamic recognition of proper circular-arc graphs ⋮ On the isomorphism problem for Helly 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
This page was built for publication: A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs
