TY - GEN
T1 - Measuring indifference: Unit interval vertex deletion
AU - Van Bevern, René
AU - Komusiewicz, Christian
AU - Moser, Hannes
AU - Niedermeier, Rolf
PY - 2010/12/21
Y1 - 2010/12/21
N2 - Making a graph unit interval by a minimum number of vertex deletions is NP-hard. The problem is motivated by applications in seriation and measuring indifference between data items. We present a fixed-parameter algorithm based on the iterative compression technique that finds in O((14k + 14) k + 1kn6) time a set of k vertices whose deletion from an n-vertex graph makes it unit interval. Additionally, we show that making a graph chordal by at most k vertex deletions is NP-complete even on {claw,net,tent}-free graphs.
AB - Making a graph unit interval by a minimum number of vertex deletions is NP-hard. The problem is motivated by applications in seriation and measuring indifference between data items. We present a fixed-parameter algorithm based on the iterative compression technique that finds in O((14k + 14) k + 1kn6) time a set of k vertices whose deletion from an n-vertex graph makes it unit interval. Additionally, we show that making a graph chordal by at most k vertex deletions is NP-complete even on {claw,net,tent}-free graphs.
UR - http://www.scopus.com/inward/record.url?scp=78650224436&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-16926-7_22
DO - 10.1007/978-3-642-16926-7_22
M3 - Conference contribution
AN - SCOPUS:78650224436
SN - 3642169252
SN - 9783642169250
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 232
EP - 243
BT - Graph-Theoretic Concepts in Computer Science - 36th International Workshop, WG 2010, Revised Papers
T2 - 36th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2010
Y2 - 28 June 2010 through 30 June 2010
ER -