@article{BBB+17,
  title =	 {Partitioning perfect graphs into stars},
  author =	 {René van Bevern and Robert Bredereck and Laurent
                  Bulteau and Jiehua Chen and Vincent Froese and Rolf
                  Niedermeier and Gerhard J. Woeginger},
  url_Preprint = {http://arxiv.org/abs/1402.2589},
  doi =		 {10.1002/jgt.22062},
  year =	 2017,
  date =	 {2017-06-01},
  journal =	 {Journal of Graph Theory},
  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 of the same size, 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.},
  volume =	 85,
  number =	 2,
  pages =	 {297--335},
  keywords =	 {algorithmic graph theory}
}

{"_id":"fXDjg9sp7M3jonPAq","bibbaseid":"vanbevern-bredereck-bulteau-chen-froese-niedermeier-woeginger-partitioningperfectgraphsintostars-2017","authorIDs":["2fwXJtKDCNhaSNr5s"],"author_short":["van Bevern, R.","Bredereck, R.","Bulteau, L.","Chen, J.","Froese, V.","Niedermeier, R.","Woeginger, G. J."],"bibdata":{"bibtype":"article","type":"article","title":"Partitioning perfect graphs into stars","author":[{"firstnames":["René"],"propositions":["van"],"lastnames":["Bevern"],"suffixes":[]},{"firstnames":["Robert"],"propositions":[],"lastnames":["Bredereck"],"suffixes":[]},{"firstnames":["Laurent"],"propositions":[],"lastnames":["Bulteau"],"suffixes":[]},{"firstnames":["Jiehua"],"propositions":[],"lastnames":["Chen"],"suffixes":[]},{"firstnames":["Vincent"],"propositions":[],"lastnames":["Froese"],"suffixes":[]},{"firstnames":["Rolf"],"propositions":[],"lastnames":["Niedermeier"],"suffixes":[]},{"firstnames":["Gerhard","J."],"propositions":[],"lastnames":["Woeginger"],"suffixes":[]}],"url_preprint":"http://arxiv.org/abs/1402.2589","doi":"10.1002/jgt.22062","year":"2017","date":"2017-06-01","journal":"Journal of Graph Theory","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 of the same size, 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.","volume":"85","number":"2","pages":"297–335","keywords":"algorithmic graph theory","bibtex":"@article{BBB+17,\n title =\t {Partitioning perfect graphs into stars},\n author =\t {René van Bevern and Robert Bredereck and Laurent\n Bulteau and Jiehua Chen and Vincent Froese and Rolf\n Niedermeier and Gerhard J. Woeginger},\n url_Preprint = {http://arxiv.org/abs/1402.2589},\n doi =\t\t {10.1002/jgt.22062},\n year =\t 2017,\n date =\t {2017-06-01},\n journal =\t {Journal of Graph Theory},\n abstract =\t {The partition of graphs into nice subgraphs is a\n central algorithmic problem with strong ties to\n matching theory. We study the partitioning of\n undirected graphs into stars of the same size, a\n problem known to be NP-complete even for the case of\n stars on three vertices. We perform a thorough\n computational complexity study of the problem on\n subclasses of perfect graphs and identify several\n polynomial-time solvable cases, for example, on\n interval graphs and bipartite permutation graphs,\n and also NP-complete cases, for example, on grid\n graphs and chordal graphs.},\n volume =\t 85,\n number =\t 2,\n pages =\t {297--335},\n keywords =\t {algorithmic graph theory}\n}\n\n","author_short":["van Bevern, R.","Bredereck, R.","Bulteau, L.","Chen, J.","Froese, V.","Niedermeier, R.","Woeginger, G. J."],"key":"BBB+17","id":"BBB+17","bibbaseid":"vanbevern-bredereck-bulteau-chen-froese-niedermeier-woeginger-partitioningperfectgraphsintostars-2017","role":"author","urls":{" preprint":"http://arxiv.org/abs/1402.2589"},"keyword":["algorithmic graph theory"],"metadata":{"authorlinks":{"van bevern, r":"https://rvb.su/"}},"downloads":0,"html":""},"bibtype":"article","biburl":"http://rvb.su/rvb.bib","creationDate":"2021-01-06T14:16:51.481Z","downloads":0,"keywords":["algorithmic graph theory"],"search_terms":["partitioning","perfect","graphs","stars","van bevern","bredereck","bulteau","chen","froese","niedermeier","woeginger"],"title":"Partitioning perfect graphs into stars","year":2017,"dataSources":["SMwzc9Bzq5Np5ikev","G5GefJqqu2DtnCZXz"]}