A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs

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

zbMATH Keywords

proper circular-arc graphsisomorphism problemsproper circular-arc canonization

Mathematics Subject Classification ID

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