{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,22]],"date-time":"2026-02-22T16:56:15Z","timestamp":1771779375141,"version":"3.50.1"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2016,12,30]],"date-time":"2016-12-30T00:00:00Z","timestamp":1483056000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"Ministry of Science and Technology (ROC)"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2018,8]]},"DOI":"10.1007\/s10878-016-0106-9","type":"journal-article","created":{"date-parts":[[2016,12,30]],"date-time":"2016-12-30T15:48:29Z","timestamp":1483112909000},"page":"532-548","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On the complete width and edge clique cover problems"],"prefix":"10.1007","volume":"36","author":[{"given":"Van Bang","family":"Le","sequence":"first","affiliation":[]},{"given":"Sheng-Lung","family":"Peng","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,12,30]]},"reference":[{"key":"106_CR1","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/0012-365X(93)90477-B","volume":"115","author":"Z Bl\u00e1zsik","year":"1993","unstructured":"Bl\u00e1zsik Z, Hujter M, Pluh\u00e1r A, Tuza Z (1993) Graphs with no induced $$C_4$$ C 4 and $$2K_2$$ 2 K 2 . Discret Math 115:51\u201355","journal-title":"Discret Math"},{"key":"106_CR2","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719796","volume-title":"Graph classes: a survey","author":"A Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt A, Le VB, Spinrad JP (1999) Graph classes: a survey. SIAM Monographs on Discrete Mathematics and Applications, Philadelphia"},{"key":"106_CR3","unstructured":"Chandler DB, Chang M-S, Kloks T, Peng S-L (2009) Probe graphs. Manuscript, http:\/\/www.cs.ccu.edu.tw\/~hunglc\/ProbeGraphs"},{"key":"106_CR4","doi-asserted-by":"crossref","first-page":"2496","DOI":"10.1016\/j.tcs.2010.10.041","volume":"412","author":"M-S Chang","year":"2011","unstructured":"Chang M-S, Hung L-J, Kloks T, Peng S-L (2011) Block-graph width. Theor Comput Sci 412:2496\u20132502","journal-title":"Theor Comput Sci"},{"key":"106_CR5","unstructured":"Chang M-S, Kloks T, Liu C-H (2012) Edge-clique graphs of cocktail parties have unbounded rankwidth. arXiv:1205.2483 [cs.DM]"},{"key":"106_CR6","unstructured":"Chang M-S, M\u00fcller H (2008) On the tree-degree of graphs. In: Proceedings 27th WG. LNCS 2204, 44\u201354"},{"key":"106_CR7","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan M, Fomin FV, Kowalik L, Lokshtanov D, Marx D, Pilipczuk M, Saurabh S (2015) Parameterized algorithms. Springer, Berlin"},{"key":"106_CR8","doi-asserted-by":"crossref","unstructured":"Cygan M, Kratsch S, Pilipczuk M, Pilipczuk M, Wahlstr\u00f6m M (2014) Clique cover and graph separation: new incompressibility results. In: ACM Transaction on Computation Theory 6","DOI":"10.1145\/2594439"},{"key":"106_CR9","doi-asserted-by":"crossref","unstructured":"Cygan M, Pilipczuky M, Pilipczuk M (2013) Known algorithms for edge clique cover are probably optimal. In: Proceedings SODA, pp 1044\u20131053","DOI":"10.1137\/1.9781611973105.75"},{"key":"106_CR10","first-page":"311","volume":"XIX","author":"S Foldes","year":"1977","unstructured":"Foldes S, Hammer PL (1977) Split graphs. Congr Numer XIX:311\u2013315","journal-title":"Congr Numer"},{"key":"106_CR11","doi-asserted-by":"crossref","unstructured":"Golumbic MC (2004) Algorithmic graph theory and perfect graphs (Second edition). Annals of Disc Math. 57, Elsevier, Amsterdam","DOI":"10.1016\/S0167-5060(04)80059-1"},{"key":"106_CR12","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511542985","volume-title":"Tolerance graphs","author":"MC Golumbic","year":"2004","unstructured":"Golumbic MC, Trenk AN (2004) Tolerance graphs. Cambridge Studies in Advanced Mathematics, New York"},{"key":"106_CR13","unstructured":"Gramm J, Guo J, H\u00fcffner F, Niedermeier R (2008) Data reduction and exact algorithms for clique cover. ACM J Exp Algorithm 13:2.2:1\u20132.2:15"},{"key":"106_CR14","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/j.cosrev.2010.01.001","volume":"4","author":"M Habib","year":"2010","unstructured":"Habib M, Paul C (2010) A survey of the algorithmic aspects of modular decomposition. Comput Sci Rev 4:41\u201359","journal-title":"Comput Sci Rev"},{"key":"106_CR15","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/0166-218X(90)90092-Q","volume":"28","author":"PL Hammer","year":"1990","unstructured":"Hammer PL, Peled UN, Sun X (1990) Difference graphs. Discret Appl Math 28:35\u201344","journal-title":"Discret Appl Math"},{"key":"106_CR16","doi-asserted-by":"crossref","first-page":"713","DOI":"10.1137\/0210054","volume":"4","author":"I Holyer","year":"1981","unstructured":"Holyer I (1981) The NP-completeness of some edge-partition problems. SIAM J Comput 4:713\u2013717","journal-title":"SIAM J Comput"},{"key":"106_CR17","first-page":"187","volume":"11","author":"DN Hoover","year":"1992","unstructured":"Hoover DN (1992) Complexity of graph covering problems for graphs of low degree. J Comb Math Comb Comput 11:187\u2013208","journal-title":"J Comb Math Comb Comput"},{"key":"106_CR18","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/0020-0190(91)90165-E","volume":"40","author":"W-L Hsu","year":"1991","unstructured":"Hsu W-L, Tsai K-H (1991) Linear time algorithms on circular-arc graphs. Inf Process Lett 40:123\u2013129","journal-title":"Inf Process Lett"},{"key":"106_CR19","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1145\/359340.359346","volume":"21","author":"LT Kou","year":"1978","unstructured":"Kou LT, Stockmeyer LJ, Wong CK (1978) Covering edges by cliques with regard to keyword conflicts and intersection graphs. Comm ACM 21:135\u2013139","journal-title":"Comm ACM"},{"key":"106_CR20","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/j.tcs.2014.12.014","volume":"568","author":"VB Le","year":"2015","unstructured":"Le VB, Peng S-L (2015) Characterizing and recognizing probe block graphs. Theor Comput Sci 568:97\u2013102","journal-title":"Theor Comput Sci"},{"key":"106_CR21","doi-asserted-by":"publisher","unstructured":"Le VB, Peng S-L (2015) Good characterizations and linear time recognition for 2-probe block graphs. In: Proceedings of the international computer symposium, Taichung, Taiwan, December 12\u201314, 2014. IOS Press, 22\u201331. doi: 10.3233\/978-1-61499-484-8-22","DOI":"10.3233\/978-1-61499-484-8-22"},{"key":"106_CR22","doi-asserted-by":"crossref","unstructured":"Le VB, Peng S-L (2015) On the complete width and edge clique cover problems. In: Proceedings of the 21st international conference COCOON 2015. Lecture Notes in Computer Science 9198, pp 537\u2013547","DOI":"10.1007\/978-3-319-21398-9_42"},{"key":"106_CR23","first-page":"151","volume":"36","author":"S Ma","year":"1989","unstructured":"Ma S, Wallis WD, Wu J (1989) Clique covering of chordal graphs. Util Math 36:151\u2013152","journal-title":"Util Math"},{"key":"106_CR24","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1016\/0166-218X(94)00022-0","volume":"52","author":"F Maffray","year":"1994","unstructured":"Maffray F, Preissmann M (1994) Linear recognition of pseudo-split graphs. Discret Appl Math 52:307\u2013312","journal-title":"Discret Appl Math"},{"key":"106_CR25","unstructured":"Mahadev NVR, Peled UN (1995) Threshold graphs and related topics. Ann Discrete Math 56, Elsevier, Amsterdam"},{"key":"106_CR26","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/0012-365X(94)00350-R","volume":"149","author":"H M\u00fcller","year":"1996","unstructured":"M\u00fcller H (1996) On edge perfectness and classes of bipartite graphs. Discret Math 149:159\u2013187","journal-title":"Discret Math"},{"key":"106_CR27","doi-asserted-by":"crossref","first-page":"406","DOI":"10.1016\/1385-7258(77)90055-5","volume":"80","author":"J Orlin","year":"1977","unstructured":"Orlin J (1977) Contentment in graph theory: covering graphs with cliques. Indag Math 80:406\u2013424","journal-title":"Indag Math"},{"key":"106_CR28","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1137\/0213005","volume":"13","author":"NJ Pullman","year":"1984","unstructured":"Pullman NJ (1984) Clique covering of graphs IV. Algorithms. SIAM J Comput 13:57\u201375","journal-title":"SIAM J Comput"},{"key":"106_CR29","first-page":"197","volume":"67","author":"A Raychaudhuri","year":"1988","unstructured":"Raychaudhuri A (1988) Intersection number and edge clique graphs of chordal and strongly chordal graphs. Congr Numer 67:197\u2013204","journal-title":"Congr Numer"},{"key":"106_CR30","doi-asserted-by":"crossref","unstructured":"Tedder M, Corneil D, Habib M, Paul C (2008) Simpler linear-time modular decomposition via recursive factorizing permutations. In: Automata, languages and programming. Lecture Notes in Computing Science 5125, pp 634\u2013645","DOI":"10.1007\/978-3-540-70575-8_52"},{"key":"106_CR31","doi-asserted-by":"crossref","first-page":"310","DOI":"10.1137\/0210022","volume":"10","author":"M Yannakakis","year":"1981","unstructured":"Yannakakis M (1981) Node-delection problems on bipartite graphs. SIAM J Comput 10:310\u2013327","journal-title":"SIAM J Comput"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-016-0106-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-016-0106-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-016-0106-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,16]],"date-time":"2019-09-16T22:49:26Z","timestamp":1568674166000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-016-0106-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,12,30]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,8]]}},"alternative-id":["106"],"URL":"https:\/\/doi.org\/10.1007\/s10878-016-0106-9","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,12,30]]}}}