$O(M\cdot N)$ Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
From MaRDI portal
Publication:4842112
DOI10.1137/S0097539793260726zbMath0831.68051MaRDI QIDQ4842112
No author found.
Publication date: 20 February 1996
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10)
Related Items
Maximum weight independent sets and cliques in intersection graphs of filaments ⋮ On the structure of certain intersection graphs ⋮ From a Circular-Arc Model to a Proper Circular-Arc Model ⋮ Solving the canonical representation and star system problems for proper circular-arc graphs in logspace ⋮ On orthogonal ray graphs ⋮ Extending partial representations of interval graphs ⋮ Filtering graphs to check isomorphism and extracting mapping by using the conductance electrical model ⋮ Circle graph isomorphism in almost linear time ⋮ Maximum max-k-clique subgraphs in cactus subtree graphs ⋮ A Simple Linear Time Algorithm for the Isomorphism Problem on Proper Circular-Arc Graphs ⋮ A simpler linear-time recognition of circular-arc graphs ⋮ Interval Routing Schemes for Circular-Arc Graphs ⋮ Practical and efficient split decomposition via graph-labelled trees ⋮ Graph isomorphism and identification matrices: Sequential algorithms ⋮ Tractabilities and intractabilities on geometric intersection graphs ⋮ Two remarks on circular arc graphs ⋮ Unit interval vertex deletion: fewer vertices are relevant ⋮ Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs ⋮ An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs ⋮ Graph isomorphism restricted by lists ⋮ Canonical representations for circular-arc graphs using flip sets ⋮ A selected tour of the theory of identification matrices ⋮ On computing the distinguishing and distinguishing chromatic numbers of interval graphs and other results ⋮ Characterizations and recognition of circular-arc graphs and subclasses: a survey ⋮ Solving the path cover problem on circular-arc graphs by using an approximation algorithm ⋮ On the isomorphism problem for Helly circular-arc graphs
