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

DOI10.1007/978-3-540-69903-3_32MaRDI QIDQ3512472zbMATH OpenOpenAlexFDO

Authors Min Chih Lin, Francisco J. Soulignac, Jayme L. 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)

Recommendations

• Circle graph isomorphism in almost linear time
• $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
• Linear time algorithms on circular-arc graphs
• scientific article; zbMATH DE number 6829367
• Circulant graphs: recognizing and isomorphism testing in polynomial time
• A solution of the isomorphism problem for circulant graphs
• A linear-time algorithm for isomorphism of a subclass of chordal graphs
• On the isomorphism problem for Helly circular-arc graphs
• Hamilton cycles in split graphs with large minimum degree

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1303554 (Why is no real title available?)
• scientific article; zbMATH DE number 512914 (Why is no real title available?)
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• $O(M\cdot N)$ Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
• A Linear Algorithm for Maximum Weight Cliques in Proper Circular Arc Graphs
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• A Simpler Linear-Time Recognition of Circular-Arc Graphs
• Algorithmic graph theory and perfect graphs
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• Certifying Algorithms for Recognizing Proper Circular-Arc Graphs and Unit Circular-Arc Graphs
• Efficient graph representations
• Fast canonization of circular strings
• Graph Classes: A Survey
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Lexicographically least circular substrings
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Linear-time recognition of circular-arc graphs
• Proper Helly Circular-Arc Graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Unit Circular-Arc Graph Representations and Feasible Circulations

Cited in

(14)

• Normal Helly circular-arc graphs and its subclasses
• $O(M\cdot N)$ Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
• On the isomorphism problem for Helly circular-arc graphs
• Fully dynamic recognition of proper circular-arc graphs
• scientific article; zbMATH DE number 512923 (Why is no real title available?)
• A certifying and dynamic algorithm for the recognition of proper circular-arc graphs
• Isomorphism of graph classes related to the circular-ones property
• scientific article; zbMATH DE number 6829367 (Why is no real title available?)
• 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
• The clique operator on circular-arc graphs
• Circle graph isomorphism in almost linear time
• Circular-arc hypergraphs: rigidity via connectedness
• Revising Johnson's table for the 21st century

This page was built for publication: A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3512472)