Interval graph representation with given interval and intersection lengths

DOI10.1007/978-3-642-35261-4_54MaRDI QIDQ4909568zbMATH OpenOpenAlexFDO

Authors Sebastian Kuhnert, Osamu Watanabe, Johannes Köbler

Publication date 21 March 2013

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-35261-4_54

zbMATH Keywords

linear time algorithminteval representations of graphslogspace algorithm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

• Interval graph representation with given interval and intersection lengths
• Realizing Interval Graphs with Size and Distance Constraints
• Recognizing graphs with fixed interval number is NP-complete
• Interval graphs with side (and size) constraints
• Interval graphs: canonical representations in logspace

Cited in

(5)

• Recognizing graphs with fixed interval number is NP-complete
• Interval graphs with side (and size) constraints
• Interval graph representation with given interval and intersection lengths
• FO model checking of interval graphs
• Graphs of interval count two with a given partition

This page was built for publication: Interval graph representation with given interval and intersection lengths

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