Interval Graphs: Canonical Representations in Logspace
From MaRDI portal
Publication:3115868
DOI10.1137/10080395XzbMath1235.05140MaRDI QIDQ3115868
Oleg Verbitsky, Sebastian Kuhnert, Bastian Laubner, Johannes Köbler
Publication date: 11 February 2012
Published in: SIAM Journal on Computing (Search for Journal in Brave)
interval graphsgraph isomorphismproper interval graphsunit interval graphsconvex graphslogspacegraph canonizationinterval hypergraphs
Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items (13)
On Compiling Structured CNFs to OBDDs ⋮ Solving the canonical representation and star system problems for proper circular-arc graphs in logspace ⋮ On compiling structured CNFs to OBDDs ⋮ Compact representation of interval graphs and circular-arc graphs of bounded degree and chromatic number ⋮ Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. Chapter I: theory ⋮ Interval graph representation with given interval and intersection lengths ⋮ Circular-arc hypergraphs: rigidity via connectedness ⋮ Unnamed Item ⋮ Graph isomorphism restricted by lists ⋮ Canonical representations for circular-arc graphs using flip sets ⋮ The Weisfeiler-Leman dimension of chordal bipartite graphs without bipartite claw ⋮ On the isomorphism problem for Helly circular-arc graphs ⋮ Cyclic arrangements with minimum modulo \(m\) winding numbers
This page was built for publication: Interval Graphs: Canonical Representations in Logspace
