Interval graphs: canonical representation in logspace

DOI10.1007/978-3-642-14165-2_33zbMATH Open1288.05281OpenAlexW1540331880MaRDI QIDQ3587393FDOQ3587393

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

Publication date: 7 September 2010

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-14165-2_33

Recommendations

• Interval graphs: canonical representations in logspace
• Around and beyond the isomorphism problem for interval graphs
• Helly circular-arc graph isomorphism is in logspace
• Interval graph representation with given interval and intersection lengths
• Canonizing Graphs of Bounded Tree Width in Logspace

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph representations (geometric and intersection representations, etc.) (05C62)

Cited In (8)

• Toll convexity
• Around and beyond the isomorphism problem for interval graphs
• Interval graph representation with given interval and intersection lengths
• The QAP-polytope and the graph isomorphism problem
• Interval graphs: canonical representations in logspace
• Helly circular-arc graph isomorphism is in logspace
• Algorithms and Computation
• Solving the canonical representation and star system problems for proper circular-arc graphs in logspace

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

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