## René van Bevern, Christian Komusiewicz, Hannes Moser, and Rolf Niedermeier.
Measuring indifference: Unit interval vertex deletion.
In *Proceedings of the 36th International Workshop on Graph
Theoretic Concepts in Computer Science (WG'10), Zarós, Crete, Greece*,
volume 6410 of *Lecture Notes in Computer Science*, pages 232–243.
Springer, 2010.

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+1)kn^6) 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.

[ bib |
DOI |
slides |
.pdf ]
Back

*This file was generated by
bibtex2html 1.98.*