Realizing Interval Graphs with Size and Distance Constraints
From MaRDI portal
Publication:4377452
DOI10.1137/S0895480196306373zbMath0884.05084OpenAlexW1964154211MaRDI QIDQ4377452
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
NP-completenessgraph algorithmscomputational biologyinterval graphsdistance constraintssize constraints
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