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 -