Standard
Star partitions of perfect graphs. / Van Bevern, René; Bredereck, Robert; Bulteau, Laurent et al.
Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings. PART 1. ed. Springer-Verlag GmbH and Co. KG, 2014. p. 174-185 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8572 LNCS, No. PART 1).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Harvard
Van Bevern, R, Bredereck, R, Bulteau, L, Chen, J, Froese, V, Niedermeier, R & Woeginger, GJ 2014,
Star partitions of perfect graphs. in
Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings. PART 1 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 1, vol. 8572 LNCS, Springer-Verlag GmbH and Co. KG, pp. 174-185, 41st International Colloquium on Automata, Languages, and Programming, ICALP 2014, Copenhagen, Denmark,
08.07.2014.
https://doi.org/10.1007/978-3-662-43948-7_15
APA
Van Bevern, R., Bredereck, R., Bulteau, L., Chen, J., Froese, V., Niedermeier, R., & Woeginger, G. J. (2014).
Star partitions of perfect graphs. In
Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings (PART 1 ed., pp. 174-185). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8572 LNCS, No. PART 1). Springer-Verlag GmbH and Co. KG.
https://doi.org/10.1007/978-3-662-43948-7_15
Vancouver
Van Bevern R, Bredereck R, Bulteau L, Chen J, Froese V, Niedermeier R et al.
Star partitions of perfect graphs. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings. PART 1 ed. Springer-Verlag GmbH and Co. KG. 2014. p. 174-185. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1). doi: 10.1007/978-3-662-43948-7_15
Author
Van Bevern, René ; Bredereck, Robert ; Bulteau, Laurent et al. /
Star partitions of perfect graphs. Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings. PART 1. ed. Springer-Verlag GmbH and Co. KG, 2014. pp. 174-185 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1).
BibTeX
@inproceedings{d9e6d6cab29f43b1be2f3a9ba313ac59,
title = "Star partitions of perfect graphs",
abstract = "The partition of graphs into nice subgraphs is a central algorithmic problem with strong ties to matching theory. We study the partitioning of undirected graphs into stars, a problem known to be NP-complete even for the case of stars on three vertices. We perform a thorough computational complexity study of the problem on subclasses of perfect graphs and identify several polynomial-time solvable cases, for example, on interval graphs and bipartite permutation graphs, and also NP-hard cases, for example, on grid graphs and chordal graphs.",
author = "{Van Bevern}, Ren{\'e} and Robert Bredereck and Laurent Bulteau and Jiehua Chen and Vincent Froese and Rolf Niedermeier and Woeginger, {Gerhard J.}",
year = "2014",
month = jan,
day = "1",
doi = "10.1007/978-3-662-43948-7_15",
language = "English",
isbn = "9783662439470",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer-Verlag GmbH and Co. KG",
number = "PART 1",
pages = "174--185",
booktitle = "Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings",
address = "Germany",
edition = "PART 1",
note = "41st International Colloquium on Automata, Languages, and Programming, ICALP 2014 ; Conference date: 08-07-2014 Through 11-07-2014",
}
RIS
TY - GEN
T1 - Star partitions of perfect graphs
AU - Van Bevern, René
AU - Bredereck, Robert
AU - Bulteau, Laurent
AU - Chen, Jiehua
AU - Froese, Vincent
AU - Niedermeier, Rolf
AU - Woeginger, Gerhard J.
PY - 2014/1/1
Y1 - 2014/1/1
N2 - The partition of graphs into nice subgraphs is a central algorithmic problem with strong ties to matching theory. We study the partitioning of undirected graphs into stars, a problem known to be NP-complete even for the case of stars on three vertices. We perform a thorough computational complexity study of the problem on subclasses of perfect graphs and identify several polynomial-time solvable cases, for example, on interval graphs and bipartite permutation graphs, and also NP-hard cases, for example, on grid graphs and chordal graphs.
AB - The partition of graphs into nice subgraphs is a central algorithmic problem with strong ties to matching theory. We study the partitioning of undirected graphs into stars, a problem known to be NP-complete even for the case of stars on three vertices. We perform a thorough computational complexity study of the problem on subclasses of perfect graphs and identify several polynomial-time solvable cases, for example, on interval graphs and bipartite permutation graphs, and also NP-hard cases, for example, on grid graphs and chordal graphs.
UR - http://www.scopus.com/inward/record.url?scp=84904164318&partnerID=8YFLogxK
U2 - 10.1007/978-3-662-43948-7_15
DO - 10.1007/978-3-662-43948-7_15
M3 - Conference contribution
AN - SCOPUS:84904164318
SN - 9783662439470
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 174
EP - 185
BT - Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings
PB - Springer-Verlag GmbH and Co. KG
T2 - 41st International Colloquium on Automata, Languages, and Programming, ICALP 2014
Y2 - 8 July 2014 through 11 July 2014
ER -
