Standard

Partitioning Perfect Graphs into Stars. / van Bevern, René; Bredereck, Robert; Bulteau, Laurent et al.

In: Journal of Graph Theory, Vol. 85, No. 2, 01.06.2017, p. 297-335.

Research output: Contribution to journal › Article › peer-review

Harvard

van Bevern, R, Bredereck, R, Bulteau, L, Chen, J, Froese, V, Niedermeier, R & Woeginger, GJ 2017, 'Partitioning Perfect Graphs into Stars', Journal of Graph Theory, vol. 85, no. 2, pp. 297-335. https://doi.org/10.1002/jgt.22062

APA

van Bevern, R., Bredereck, R., Bulteau, L., Chen, J., Froese, V., Niedermeier, R., & Woeginger, G. J. (2017). Partitioning Perfect Graphs into Stars. Journal of Graph Theory, 85(2), 297-335. https://doi.org/10.1002/jgt.22062

Vancouver

van Bevern R, Bredereck R, Bulteau L, Chen J, Froese V, Niedermeier R et al. Partitioning Perfect Graphs into Stars. Journal of Graph Theory. 2017 Jun 1;85(2):297-335. doi: 10.1002/jgt.22062

Author

van Bevern, René ; Bredereck, Robert ; Bulteau, Laurent et al. / Partitioning Perfect Graphs into Stars. In: Journal of Graph Theory. 2017 ; Vol. 85, No. 2. pp. 297-335.

BibTeX

@article{2ddc754102e944d6a790beec73461a51,
title = "Partitioning Perfect Graphs into Stars",
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 same-size 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-complete cases, for example, on grid graphs and chordal graphs.",
keywords = "generalized matching problem, graph algorithms, graph factors, graph packing, P-Partition, INTERVAL-GRAPHS, PATH PARTITION, P-3-PARTITION, ORIENTATIONS, RECOGNITION ALGORITHM, COMPLEXITY, CHORDAL GRAPHS, BIPARTITE GRAPHS, P -Partition",
author = "{van Bevern}, Ren{\'e} and Robert Bredereck and Laurent Bulteau and Jiehua Chen and Vincent Froese and Rolf Niedermeier and Woeginger, {Gerhard J.}",
note = "Publisher Copyright: {\textcopyright} 2016 Wiley Periodicals, Inc.",
year = "2017",
month = jun,
day = "1",
doi = "10.1002/jgt.22062",
language = "English",
volume = "85",
pages = "297--335",
journal = "Journal of Graph Theory",
issn = "0364-9024",
publisher = "Wiley-Blackwell",
number = "2",

}

RIS

TY - JOUR

T1 - Partitioning Perfect Graphs into Stars

AU - van Bevern, René

AU - Bredereck, Robert

AU - Bulteau, Laurent

AU - Chen, Jiehua

AU - Froese, Vincent

AU - Niedermeier, Rolf

AU - Woeginger, Gerhard J.

N1 - Publisher Copyright: © 2016 Wiley Periodicals, Inc.

PY - 2017/6/1

Y1 - 2017/6/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 same-size 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-complete 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 same-size 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-complete cases, for example, on grid graphs and chordal graphs.

KW - generalized matching problem

KW - graph algorithms

KW - graph factors

KW - graph packing

KW - P-Partition

KW - INTERVAL-GRAPHS

KW - PATH PARTITION

KW - P-3-PARTITION

KW - ORIENTATIONS

KW - RECOGNITION ALGORITHM

KW - COMPLEXITY

KW - CHORDAL GRAPHS

KW - BIPARTITE GRAPHS

KW - P -Partition

UR - http://www.scopus.com/inward/record.url?scp=84977137901&partnerID=8YFLogxK

U2 - 10.1002/jgt.22062

DO - 10.1002/jgt.22062

M3 - Article

AN - SCOPUS:84977137901

VL - 85

SP - 297

EP - 335

JO - Journal of Graph Theory

JF - Journal of Graph Theory

SN - 0364-9024

IS - 2

ER -

ID: 9087955