Realizing Interval Graphs with Size and Distance Constraints

DOI10.1137/S0895480196306373zbMath0884.05084OpenAlexW1964154211MaRDI QIDQ4377452

Ron Shamir, Itsik Pe'er

Publication date: 9 February 1998

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

NP-completenessgraph algorithmscomputational biologyinterval graphsdistance constraintssize constraints

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (9)

Dimension of restricted classes of interval orders ⋮ Extending partial representations of interval graphs ⋮ Stick graphs with length constraints ⋮ Recognizing Stick Graphs with and without Length Constraints ⋮ Interval graph representation with given interval and intersection lengths ⋮ Minimal obstructions for partial representations of interval graphs ⋮ Graphs of interval count two with a given partition ⋮ Interval orders with two interval lengths ⋮ Point placement on the line by distance data.

This page was built for publication: Realizing Interval Graphs with Size and Distance Constraints