Interval graphs: canonical representation in logspace

DOI10.1007/978-3-642-14165-2_33MaRDI QIDQ3587393zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

Cited in

(8)

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

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)