Realizing Interval Graphs with Size and Distance Constraints

DOI10.1137/S0895480196306373zbMath0884.05084MaRDI QIDQ4377452

Ron Shamir, Itsik Pe'er

Publication date: 9 February 1998

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

zbMATH Keywords

NP-completeness; graph algorithms; computational biology; interval graphs; distance constraints; size constraints

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Point placement on the line by distance data.