Star partitions of perfect graphs

R. Bevern, van; R. Bredereck; L. Bulteau; J. Chen; V. Froese; R. Niedermeier; G.J. Woeginger

doi:10.1007/978-3-662-43948-7_15

Star partitions of perfect graphs

R. Bevern, van
, R. Bredereck
, L. Bulteau
, J. Chen
, V. Froese
, R. Niedermeier
, G.J. Woeginger

Discrete Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

8 Citations (Scopus)

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.

Original language	English
Title of host publication	Automata, Languages and Programming (41st International Colloquium, ICALP 2014, Copenhagen, Denmark, Switzerland, July 8-11, 2014. Proceedings, Part I)
Editors	J. Esparza, P. Fraigniard, T. Husfeldt, E. Koutsoupias
Place of Publication	Berlin
Publisher	Springer
Pages	174-185
ISBN (Print)	978-3-662-43947-0
DOIs	https://doi.org/10.1007/978-3-662-43948-7_15
Publication status	Published - 2014
Event	41st International Colloquium on Automata, Languages and Programming (ICALP 2014) - Copenhagen, Denmark Duration: 8 Jun 2014 → 11 Jun 2014 Conference number: 41

Publication series

Name	Lecture Notes in Computer Science
Volume	8572
ISSN (Print)	0302-9743

Conference

Conference	41st International Colloquium on Automata, Languages and Programming (ICALP 2014)
Abbreviated title	ICALP 2014
Country/Territory	Denmark
City	Copenhagen
Period	8/06/14 → 11/06/14

Access to Document

10.1007/978-3-662-43948-7_15

Cite this

Bevern, van, R., Bredereck, R., Bulteau, L., Chen, J., Froese, V., Niedermeier, R., & Woeginger, G. J. (2014). Star partitions of perfect graphs. In J. Esparza, P. Fraigniard, T. Husfeldt, & E. Koutsoupias (Eds.), Automata, Languages and Programming (41st International Colloquium, ICALP 2014, Copenhagen, Denmark, Switzerland, July 8-11, 2014. Proceedings, Part I) (pp. 174-185). (Lecture Notes in Computer Science; Vol. 8572). Springer. https://doi.org/10.1007/978-3-662-43948-7_15

Bevern, van, R. ; Bredereck, R. ; Bulteau, L. et al. / Star partitions of perfect graphs. Automata, Languages and Programming (41st International Colloquium, ICALP 2014, Copenhagen, Denmark, Switzerland, July 8-11, 2014. Proceedings, Part I). editor / J. Esparza ; P. Fraigniard ; T. Husfeldt ; E. Koutsoupias. Berlin : Springer, 2014. pp. 174-185 (Lecture Notes in Computer Science).

@inproceedings{7854acc649c44232a80325411a7a3cbf,

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 = "\{Bevern, van\}, R. and R. Bredereck and L. Bulteau and J. Chen and V. Froese and R. Niedermeier and G.J. Woeginger",

year = "2014",

doi = "10.1007/978-3-662-43948-7\_15",

language = "English",

isbn = "978-3-662-43947-0",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "174--185",

editor = "J. Esparza and P. Fraigniard and T. Husfeldt and E. Koutsoupias",

booktitle = "Automata, Languages and Programming (41st International Colloquium, ICALP 2014, Copenhagen, Denmark, Switzerland, July 8-11, 2014. Proceedings, Part I)",

address = "Germany",

note = "41st International Colloquium on Automata, Languages and Programming (ICALP 2014), ICALP 2014 ; Conference date: 08-06-2014 Through 11-06-2014",

}

Bevern, van, R, Bredereck, R, Bulteau, L, Chen, J, Froese, V, Niedermeier, R & Woeginger, GJ 2014, Star partitions of perfect graphs. in J Esparza, P Fraigniard, T Husfeldt & E Koutsoupias (eds), Automata, Languages and Programming (41st International Colloquium, ICALP 2014, Copenhagen, Denmark, Switzerland, July 8-11, 2014. Proceedings, Part I). Lecture Notes in Computer Science, vol. 8572, Springer, Berlin, pp. 174-185, 41st International Colloquium on Automata, Languages and Programming (ICALP 2014), Copenhagen, Denmark, 8/06/14. https://doi.org/10.1007/978-3-662-43948-7_15

Star partitions of perfect graphs. / Bevern, van, R.; Bredereck, R.; Bulteau, L. et al.
Automata, Languages and Programming (41st International Colloquium, ICALP 2014, Copenhagen, Denmark, Switzerland, July 8-11, 2014. Proceedings, Part I). ed. / J. Esparza; P. Fraigniard; T. Husfeldt; E. Koutsoupias. Berlin: Springer, 2014. p. 174-185 (Lecture Notes in Computer Science; Vol. 8572).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Star partitions of perfect graphs

AU - Bevern, van, R.

AU - Bredereck, R.

AU - Bulteau, L.

AU - Chen, J.

AU - Froese, V.

AU - Niedermeier, R.

AU - Woeginger, G.J.

N1 - Conference code: 41

PY - 2014

Y1 - 2014

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.

U2 - 10.1007/978-3-662-43948-7_15

DO - 10.1007/978-3-662-43948-7_15

M3 - Conference contribution

SN - 978-3-662-43947-0

T3 - Lecture Notes in Computer Science

SP - 174

EP - 185

BT - Automata, Languages and Programming (41st International Colloquium, ICALP 2014, Copenhagen, Denmark, Switzerland, July 8-11, 2014. Proceedings, Part I)

A2 - Esparza, J.

A2 - Fraigniard, P.

A2 - Husfeldt, T.

A2 - Koutsoupias, E.

PB - Springer

CY - Berlin

T2 - 41st International Colloquium on Automata, Languages and Programming (ICALP 2014)

Y2 - 8 June 2014 through 11 June 2014

ER -

Bevern, van R, Bredereck R, Bulteau L, Chen J, Froese V, Niedermeier R et al. Star partitions of perfect graphs. In Esparza J, Fraigniard P, Husfeldt T, Koutsoupias E, editors, Automata, Languages and Programming (41st International Colloquium, ICALP 2014, Copenhagen, Denmark, Switzerland, July 8-11, 2014. Proceedings, Part I). Berlin: Springer. 2014. p. 174-185. (Lecture Notes in Computer Science). doi: 10.1007/978-3-662-43948-7_15

Star partitions of perfect graphs

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this