Standard
Measuring indifference: Unit interval vertex deletion. / Van Bevern, René; Komusiewicz, Christian; Moser, Hannes et al.
Graph-Theoretic Concepts in Computer Science - 36th International Workshop, WG 2010, Revised Papers. 2010. p. 232-243 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6410 LNCS).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Harvard
Van Bevern, R, Komusiewicz, C, Moser, H & Niedermeier, R 2010,
Measuring indifference: Unit interval vertex deletion. in
Graph-Theoretic Concepts in Computer Science - 36th International Workshop, WG 2010, Revised Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6410 LNCS, pp. 232-243, 36th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2010, Zaros, Crete, Greece,
28.06.2010.
https://doi.org/10.1007/978-3-642-16926-7_22
APA
Vancouver
Van Bevern R, Komusiewicz C, Moser H, Niedermeier R.
Measuring indifference: Unit interval vertex deletion. In Graph-Theoretic Concepts in Computer Science - 36th International Workshop, WG 2010, Revised Papers. 2010. p. 232-243. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-16926-7_22
Author
Van Bevern, René ; Komusiewicz, Christian ; Moser, Hannes et al. /
Measuring indifference: Unit interval vertex deletion. Graph-Theoretic Concepts in Computer Science - 36th International Workshop, WG 2010, Revised Papers. 2010. pp. 232-243 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
BibTeX
@inproceedings{38d5aa53b14640a09db9f9cc1b72cfd3,
title = "Measuring indifference: Unit interval vertex deletion",
abstract = "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.",
author = "{Van Bevern}, Ren{\'e} and Christian Komusiewicz and Hannes Moser and Rolf Niedermeier",
year = "2010",
month = dec,
day = "21",
doi = "10.1007/978-3-642-16926-7_22",
language = "English",
isbn = "3642169252",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "232--243",
booktitle = "Graph-Theoretic Concepts in Computer Science - 36th International Workshop, WG 2010, Revised Papers",
note = "36th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2010 ; Conference date: 28-06-2010 Through 30-06-2010",
}
RIS
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 -
