Interval graphs: canonical representations in logspace

DOI10.1137/10080395XMaRDI QIDQ3115868zbMATH OpenFDO

Authors Sebastian Kuhnert, Bastian Laubner, Oleg Verbitsky, Johannes Köbler

Publication date 11 February 2012

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/10080395X

zbMATH Keywords

convex graphsgraph canonizationgraph isomorphisminterval graphsinterval hypergraphslogspaceproper interval graphsunit interval graphs

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Interval graphs: canonical representation in logspace
• Around and beyond the isomorphism problem for interval graphs
• Helly circular-arc graph isomorphism is in logspace
• Solving the canonical representation and star system problems for proper circular-arc graphs in logspace
• Solving the canonical representation and star system problems for proper circular-arc graphs in logspace

Cited in

(19)

• Canonical representations for circular-arc graphs using flip sets
• The Weisfeiler-Leman dimension of chordal bipartite graphs without bipartite claw
• Cyclic arrangements with minimum modulo \(m\) winding numbers
• On compiling structured CNFs to OBDDs
• On the isomorphism problem for Helly circular-arc graphs
• Compact representation of interval graphs and circular-arc graphs of bounded degree and chromatic number
• Solving the canonical representation and star system problems for proper circular-arc graphs in logspace
• Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. I: Theory
• On compiling structured CNFs to OBDDs
• Solving the canonical representation and star system problems for proper circular-arc graphs in logspace
• Interval graphs: canonical representation in logspace
• Around and beyond the isomorphism problem for interval graphs
• Interval graph representation with given interval and intersection lengths
• Interval graph representation with given interval and intersection lengths
• scientific article; zbMATH DE number 7561610 (Why is no real title available?)
• Circular-arc hypergraphs: rigidity via connectedness
• Algorithms and Computation
• Graph isomorphism restricted by lists
• Canonizing graphs of bounded rank-width in parallel via Weisfeiler-Leman

This page was built for publication: Interval graphs: canonical representations in logspace

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