Measuring Indifference: Unit Interval Vertex Deletion (Homepage of René van Bevern)

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, June 2010. Volume 6410 in Lecture Notes in Computer Science, pages 232–243, Springer.

Making a graph unit interval by a minimum number of vertex deletions is NP-complete. 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+1kn⁶) time a set of k vertices whose deletion from an n-vertex graph makes it unit interval.

Download

The paper is availabe in PDF format. Missing proofs can be found in Chapter 5 of my Diploma thesis. Slides of a talk are available. The original publication can be found on SpringerLink.

BibTex Entry

For information on using BibTex in your LaTeX documents, refer to the chapter "Bibliography management" in the wikibook for LaTeX.

@inproceedings{BKMN10,
  author = {Ren{\'e} van Bevern and Christian Komusiewicz
    and Hannes Moser and Rolf Niedermeier},
  title = {Measuring Indifference: Unit Interval Vertex
    Deletion},
  booktitle = {Proceedings of the 36th International 
    Workshop on Graph Theoretic Concepts in Computer 
    Science (WG'10)},
  publisher = {Springer-Verlag Berlin, Germany},
  address = {Zar{\'o}s, Crete, Greece},
  year = {2010},
  month = {June},
  series = {Lecture Notes in Computer Science},
  volume = {6410},
  pages = {232--243},
  note = {To appear}
}