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.