{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T01:45:33Z","timestamp":1725500733895},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642360640"},{"type":"electronic","value":"9783642360657"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-36065-7_19","type":"book-chapter","created":{"date-parts":[[2013,1,21]],"date-time":"2013-01-21T16:36:53Z","timestamp":1358786213000},"page":"194-205","source":"Crossref","is-referenced-by-count":1,"title":["Triangle-Partitioning Edges of Planar Graphs, Toroidal Graphs and k-Planar Graphs"],"prefix":"10.1007","author":[{"given":"Jiawei","family":"Gao","sequence":"first","affiliation":[]},{"given":"Ton","family":"Kloks","sequence":"additional","affiliation":[]},{"given":"Sheung-Hung","family":"Poon","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"19_CR1","doi-asserted-by":"crossref","unstructured":"Ausiello, G., Creszensi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation: Combinatorial optimization problems and their approximability properties. Springer (1999)","DOI":"10.1007\/978-3-642-58412-1"},{"key":"19_CR2","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"B. Baker","year":"1994","unstructured":"Baker, B.: Approximation algorithms for NP-complete problems. Journal of the ACM\u00a041, 153\u2013180 (1994)","journal-title":"Journal of the ACM"},{"key":"19_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"H. Bodlaender","year":"1998","unstructured":"Bodlaender, H.: A partial k-arboretum of graphs of bounded treewidth. Theoretical Computer Science\u00a0209, 1\u201345 (1998)","journal-title":"Theoretical Computer Science"},{"key":"19_CR4","first-page":"421","volume":"10","author":"N. Bruijn de","year":"1948","unstructured":"de Bruijn, N., Erd\u00f6s, P.: On a combinatorial problem. Indagationes Mathematicae\u00a010, 421\u2013423 (1948)","journal-title":"Indagationes Mathematicae"},{"key":"19_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1007\/3-540-45477-2_6","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"M.-S. Chang","year":"2001","unstructured":"Chang, M.-S., M\u00fcller, H.: On the Tree-Degree of Graphs. In: Brandst\u00e4dt, A., Le, V.B. (eds.) WG 2001. LNCS, vol.\u00a02204, pp. 44\u201354. Springer, Heidelberg (2001)"},{"key":"19_CR6","first-page":"1203","volume":"ArXiV","author":"M. Cygan","year":"2012","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M.: Known algorithms for edge clique cover are probably optimal. Manuscript ArXiV: 1203.1754v1 (2012)","journal-title":"Manuscript"},{"key":"19_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1007\/978-3-642-24983-9_9","volume-title":"Computational Geometry, Graphs and Applications","author":"R. Fleischer","year":"2011","unstructured":"Fleischer, R., Wu, X.: Edge Clique Partition of K\n                  4-Free and Planar Graphs. In: Akiyama, J., Bo, J., Kano, M., Tan, X. (eds.) CGGA 2010. LNCS, vol.\u00a07033, pp. 84\u201395. Springer, Heidelberg (2011)"},{"key":"19_CR8","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1016\/j.disc.2007.12.075","volume":"309","author":"A. Gagarin","year":"2009","unstructured":"Gagarin, A., Myrvold, W., Chambers, J.: The obstructions for toroidal graphs with no K\n                  3,3\u2019s. Discrete Mathematics\u00a0309, 513\u2013520 (2009)","journal-title":"Discrete Mathematics"},{"key":"19_CR9","doi-asserted-by":"crossref","unstructured":"Gramm, J., Guo, J., H\u00fcffner, F., Niedermeier, R.: Data reduction, exact, and heuristic algorithms for clique cover. In: Proceedings ALENEX, pp. 86\u201394. SIAM (2006)","DOI":"10.1137\/1.9781611972863.9"},{"key":"19_CR10","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/0012-365X(90)90168-H","volume":"85","author":"A. Gy\u00e1rf\u00e1s","year":"1990","unstructured":"Gy\u00e1rf\u00e1s, A.: A simple lowerbound on edge clique covering by cliques. Discrete Mathematics\u00a085, 103\u2013104 (1990)","journal-title":"Discrete Mathematics"},{"key":"19_CR11","doi-asserted-by":"publisher","first-page":"713","DOI":"10.1137\/0210054","volume":"10","author":"I. Holyer","year":"1981","unstructured":"Holyer, I.: The NP-completeness of some edge-partition problems. SIAM J. Comput.\u00a010, 713\u2013717 (1981)","journal-title":"SIAM J. Comput."},{"key":"19_CR12","first-page":"187","volume":"11","author":"D. Hoover","year":"1992","unstructured":"Hoover, D.: Complexity of graph covering problems for graphs of low degree. JCMCC\u00a011, 187\u2013208 (1992)","journal-title":"JCMCC"},{"key":"19_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth","author":"T. Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth. LNCS, vol.\u00a0842. Springer, Heidelberg (1994)"},{"key":"19_CR14","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1145\/359340.359346","volume":"21","author":"L. Kou","year":"1978","unstructured":"Kou, L., Stockmeyer, L., Wong, C.: Covering edges by cliques with regard to keyword conflicts and intersection graphs. Comm. ACM\u00a021, 135\u2013139 (1978)","journal-title":"Comm. ACM"},{"key":"19_CR15","unstructured":"Laroche, P.: Planar 1-in-3 satisfiability is NP-complete. Comptes Rendus de l\u2019Acade\u2019mie des Sciences, Se\u2019rie 1, Mathe\u2019matique\u00a0316(4), 389\u2013392 (1993)"},{"key":"19_CR16","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R. Lipton","year":"1979","unstructured":"Lipton, R., Tarjan, R.: A separator theorem for planar graphs. SIAM Journal on Applied Mathematics\u00a036, 177\u2013189 (1979)","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"19_CR17","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"R. Lipton","year":"1980","unstructured":"Lipton, R., Tarjan, R.: Applications of a planar separator theorem. SIAM Journal on Computing\u00a09, 615\u2013627 (1980)","journal-title":"SIAM Journal on Computing"},{"key":"19_CR18","unstructured":"Mujuni, E., Rosamond, F.: Parameterized complexity of the clique partition problem. In: Proceedings CATS, vol.\u00a077, pp. 75\u201378. Australian Computer Society (2008)"},{"key":"19_CR19","doi-asserted-by":"crossref","unstructured":"Orlin, J.: Contentment in graph theory: covering graphs with cliques. Proceedings of the Nederlandse Academie van Wetenschappen, Amsterdam. Series A\u00a080, 406\u2013424 (1977)","DOI":"10.1016\/1385-7258(77)90055-5"},{"key":"19_CR20","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/0213005","volume":"13","author":"N. Pullman","year":"1984","unstructured":"Pullman, N.: Clique covering of graphs IV. Algorithms. SIAM Journal on Computing\u00a013, 57\u201375 (1984)","journal-title":"SIAM Journal on Computing"},{"key":"19_CR21","unstructured":"Shaohan, M., Wallis, W., Lin, W.: The complexity of the clique partition number problem. In: Nineteenth Southeastern Conference on Combinatorics, Graph Theory and Computing, Congr. Numer., vol.\u00a067, pp. 59\u201366 (1988)"},{"key":"19_CR22","unstructured":"Surhone, L., Tennoe, M., Henssonow, S. (eds.): Toroidal graph. Betascript Publishing (2010)"},{"key":"19_CR23","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/0012-365X(85)90051-2","volume":"55","author":"R. Tarjan","year":"1985","unstructured":"Tarjan, R.: Decomposition by clique separators. Discrete Mathematics\u00a055, 221\u2013232 (1985)","journal-title":"Discrete Mathematics"},{"key":"19_CR24","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L. Valiant","year":"1979","unstructured":"Valiant, L.: The complexity of computing the permanent. Theoretical Computer Science\u00a08, 189\u2013201 (1979)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-36065-7_19.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T13:34:55Z","timestamp":1620135295000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-36065-7_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642360640","9783642360657"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-36065-7_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}