{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,15]],"date-time":"2025-11-15T10:17:23Z","timestamp":1763201843058},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662439470"},{"type":"electronic","value":"9783662439487"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43948-7_15","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T16:10:36Z","timestamp":1402503036000},"page":"174-185","source":"Crossref","is-referenced-by-count":5,"title":["Star Partitions of Perfect Graphs"],"prefix":"10.1007","author":[{"given":"Ren\u00e9","family":"van Bevern","sequence":"first","affiliation":[]},{"given":"Robert","family":"Bredereck","sequence":"additional","affiliation":[]},{"given":"Laurent","family":"Bulteau","sequence":"additional","affiliation":[]},{"given":"Jiehua","family":"Chen","sequence":"additional","affiliation":[]},{"given":"Vincent","family":"Froese","sequence":"additional","affiliation":[]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[]},{"given":"Gerhard J.","family":"Woeginger","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1-3","key":"15_CR1","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1016\/j.tcs.2007.05.012","volume":"381","author":"K. Asdre","year":"2007","unstructured":"Asdre, K., Nikolopoulos, S.D.: NP-completeness results for some problems on subclasses of bipartite and chordal graphs. Theor. Comput. Sci.\u00a0381(1-3), 248\u2013259 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"15_CR2","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0196-6774(90)90001-U","volume":"11","author":"F. Berman","year":"1990","unstructured":"Berman, F., Johnson, D., Leighton, T., Shor, P.W., Snyder, L.: Generalized planar matching. J. Algorithms\u00a011(2), 153\u2013184 (1990)","journal-title":"J. Algorithms"},{"doi-asserted-by":"crossref","unstructured":"van Bevern, R., Bredereck, R., Chen, J., Froese, V., Niedermeier, R., Woeginger, G.J.: Star partitions of perfect graphs, TU Berlin (2014a) (manuscript) arXiv:1402.2589 [cs.DM]","key":"15_CR3","DOI":"10.1007\/978-3-662-43948-7_15"},{"doi-asserted-by":"crossref","unstructured":"van Bevern, R., Bredereck, R., Chen, J., Froese, V., Niedermeier, R., Woeginger, G.J.: Network-based dissolution, TU Berlin (2014b) (manuscript) arXiv:1402.2664 [cs.DM]","key":"15_CR4","DOI":"10.1007\/978-3-662-44465-8_7"},{"doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes: a Survey. In: SIAM Monographs on Discrete Mathematics and Applications, vol.\u00a03. SIAM (1999)","key":"15_CR5","DOI":"10.1137\/1.9780898719796"},{"key":"15_CR6","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/j.dam.2012.08.026","volume":"168","author":"J. Chalopin","year":"2014","unstructured":"Chalopin, J., Paulusma, D.: Packing bipartite graphs with covers of complete bipartite graphs. Discrete Appl. Math.\u00a0168, 40\u201350 (2014)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"15_CR7","doi-asserted-by":"publisher","first-page":"926","DOI":"10.1137\/0214065","volume":"14","author":"D. Corneil","year":"1985","unstructured":"Corneil, D., Perl, Y., Stewart, L.: A linear recognition algorithm for cographs. SIAM J. Comput.\u00a014(4), 926\u2013934 (1985)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"15_CR8","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/0095-8956(88)90068-8","volume":"45","author":"G. Cornu\u00e9jols","year":"1988","unstructured":"Cornu\u00e9jols, G.: General factors of graphs. J. Combin. Theory Ser. B\u00a045(2), 185\u2013198 (1988)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"1-3","key":"15_CR9","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/S0166-218X(98)00006-7","volume":"84","author":"E. Dahlhaus","year":"1998","unstructured":"Dahlhaus, E., Karpinski, M.: Matching and multidimensional matching in chordal and strongly chordal graphs. Discrete Appl. Math.\u00a084(1-3), 79\u201391 (1998)","journal-title":"Discrete Appl. Math."},{"issue":"1-3","key":"15_CR10","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1007\/s10107-003-0414-6","volume":"98","author":"K.M.J. De Bontridder","year":"2003","unstructured":"De Bontridder, K.M.J., Halld\u00f3rsson, B.V., Halld\u00f3rsson, M.M., Hurkens, C.A.J., Lenstra, J.K., Ravi, R., Stougie, L.: Approximation algorithms for the test cover problem. Math. Program.\u00a098(1-3), 477\u2013491 (2003)","journal-title":"Math. Program."},{"issue":"2","key":"15_CR11","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/0166-218X(85)90008-3","volume":"10","author":"M.E. Dyer","year":"1985","unstructured":"Dyer, M.E., Frieze, A.M.: On the complexity of partitioning graphs into connected subgraphs. Discrete Appl. Math.\u00a010(2), 139\u2013153 (1985)","journal-title":"Discrete Appl. Math."},{"key":"15_CR12","series-title":"Annals of Discrete Mathematics","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M.C. Golumbic","year":"2004","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Annals of Discrete Mathematics. Elsevier, Amsterdam (2004)"},{"issue":"3","key":"15_CR13","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1137\/0212040","volume":"12","author":"D.G. Kirkpatrick","year":"1983","unstructured":"Kirkpatrick, D.G., Hell, P.: On the complexity of general graph factor problems. SIAM J. Comput.\u00a012(3), 601\u2013608 (1983)","journal-title":"SIAM J. Comput."},{"key":"15_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1002","DOI":"10.1007\/11752578_121","volume-title":"Parallel Processing and Applied Mathematics","author":"A. Kosowski","year":"2006","unstructured":"Kosowski, A., Ma\u0142afiejski, M., \u017byli\u0144ski, P.: Parallel processing subsystems with redundancy in\u00a0a\u00a0distributed environment. In: Wyrzykowski, R., Dongarra, J., Meyer, N., Wa\u015bniewski, J. (eds.) PPAM 2005. LNCS, vol.\u00a03911, pp. 1002\u20131009. Springer, Heidelberg (2006)"},{"key":"15_CR15","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1007\/11424758_68","volume-title":"Computational Science and Its Applications \u2013 ICCSA 2005","author":"M. Ma\u0142afiejski","year":"2005","unstructured":"Ma\u0142afiejski, M., \u017byli\u0144ski, P.: Weakly cooperative guards in grids. In: Gervasi, O., Gavrilova, M.L., Kumar, V., Lagan\u00e1, A., Lee, H.P., Mun, Y., Taniar, D., Tan, C.J.K. (eds.) ICCSA 2005. LNCS, vol.\u00a03480, pp. 647\u2013656. Springer, Heidelberg (2005)"},{"issue":"5","key":"15_CR16","doi-asserted-by":"publisher","first-page":"677","DOI":"10.1016\/j.orl.2006.12.004","volume":"35","author":"J. Monnot","year":"2007","unstructured":"Monnot, J., Toulouse, S.: The path partition problem and related problems in bipartite graphs. Oper. Res. Lett.\u00a035(5), 677\u2013684 (2007)","journal-title":"Oper. Res. Lett."},{"issue":"4","key":"15_CR17","doi-asserted-by":"crossref","first-page":"687","DOI":"10.1007\/s00224-012-9412-5","volume":"52","author":"J.M.M. Rooij van","year":"2013","unstructured":"van Rooij, J.M.M., van Kooten Niekerk, M.E., Bodlaender, H.L.: Partition into triangles on bounded degree graphs. Theory Comput. Syst.\u00a052(4), 687\u2013718 (2013)","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"15_CR18","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1007\/BF02187706","volume":"1","author":"P. Rosenstiehl","year":"1986","unstructured":"Rosenstiehl, P., Tarjan, R.E.: Rectilinear planar layouts and bipolar orientations of planar graphs. Discrete Comput. Geom.\u00a01(1), 343\u2013353 (1986)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"15_CR19","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1016\/S0166-218X(87)80003-3","volume":"18","author":"J. Spinrad","year":"1987","unstructured":"Spinrad, J., Brandst\u00e4dt, A., Stewart, L.: Bipartite permutation graphs. Discrete Appl. Math.\u00a018(3), 279\u2013292 (1987)","journal-title":"Discrete Appl. Math."},{"key":"15_CR20","first-page":"89","volume":"147","author":"G. Steiner","year":"2000","unstructured":"Steiner, G.: On the k-path partition problem in cographs. Congressus Numerantium\u00a0147, 89\u201396 (2000)","journal-title":"Congressus Numerantium"},{"issue":"3","key":"15_CR21","doi-asserted-by":"publisher","first-page":"2147","DOI":"10.1016\/S0304-3975(02)00577-7","volume":"290","author":"G. Steiner","year":"2003","unstructured":"Steiner, G.: On the k-path partition of graphs. Theor. Comput. Sci.\u00a0290(3), 2147\u20132155 (2003)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"15_CR22","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1145\/322326.322328","volume":"29","author":"K. Takamizawa","year":"1982","unstructured":"Takamizawa, K., Nishizeki, T., Saito, N.: Linear-time computability of combinatorial problems on series-parallel graphs. J. ACM\u00a029(3), 623\u2013641 (1982)","journal-title":"J. ACM"},{"issue":"3","key":"15_CR23","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/0166-218X(96)00094-7","volume":"69","author":"J.-H. Yan","year":"1996","unstructured":"Yan, J.-H., Chen, J.-J., Chang, G.J.: Quasi-threshold graphs. Discrete Appl. Math.\u00a069(3), 247\u2013255 (1996)","journal-title":"Discrete Appl. Math."},{"issue":"1-3","key":"15_CR24","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/S0166-218X(97)00012-7","volume":"78","author":"J.-H. Yan","year":"1997","unstructured":"Yan, J.-H., Chang, G.J., Hedetniemi, S.M., Hedetniemi, S.T.: k-path partitions in trees. Discrete Appl. Math.\u00a078(1-3), 227\u2013233 (1997)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"15_CR25","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/j.cosrev.2007.07.002","volume":"1","author":"R. Yuster","year":"2007","unstructured":"Yuster, R.: Combinatorial and computational aspects of graph packing and graph decomposition. Computer Science Review\u00a01(1), 12\u201326 (2007)","journal-title":"Computer Science Review"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-43948-7_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T02:39:16Z","timestamp":1558924756000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43948-7_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439470","9783662439487"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43948-7_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}