{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T08:41:31Z","timestamp":1770280891231,"version":"3.49.0"},"reference-count":22,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2012,3]]},"abstract":"<jats:p> Many fixed-parameter tractable algorithms using a bounded search tree have been repeatedly improved, often by describing a larger number of branching rules involving an increasingly complex case analysis. We introduce a novel and general search strategy that branches on the forbidden subgraphs of a graph class relaxation. By using the class of P<jats:sub>4<\/jats:sub>-sparse graphs as the relaxed graph class, we obtain efficient bounded search tree algorithms for several parametrized deletion problems. We give the first non-trivial bounded search tree algorithms for the cograph edge-deletion problem and the trivially perfect edge-deletion problems. For the cograph vertex deletion problem, a refined analysis of the runtime of our simple bounded search algorithm gives a faster exponential factor than those algorithms designed with the help of complicated case distinctions and non-trivial running time analysis [R. Niedermeier and P. Rossmanith, An efficient fixed-parameter algorithm for 3-hitting set, J. Discrete Algorithms1(1) (2003) 89\u2013102] and computer-aided branching rules [J. Gramm, J. Guo, F. H\u00fcffner and R. Niedermeier, Automated generation of search tree algorithms for hard graph modification problems, Algorithmica39(4) (2004) 321\u2013347]. <\/jats:p>","DOI":"10.1142\/s1793830912500085","type":"journal-article","created":{"date-parts":[[2012,4,10]],"date-time":"2012-04-10T01:24:02Z","timestamp":1334021042000},"page":"1250008","source":"Crossref","is-referenced-by-count":14,"title":["BOUNDED SEARCH TREE ALGORITHMS FOR PARAMETRIZED COGRAPH DELETION: EFFICIENT BRANCHING RULES BY EXPLOITING STRUCTURES OF SPECIAL GRAPH CLASSES"],"prefix":"10.1142","volume":"04","author":[{"given":"JAMES","family":"NASTOS","sequence":"first","affiliation":[{"name":"Department of Computer Science, Irving K. Barber School of Arts and Sciences, University of British Columbia Okanagan, Kelowna, Canada V1V 1V7, Canada"}]},{"given":"YONG","family":"GAO","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Irving K. Barber School of Arts and Sciences, University of British Columbia Okanagan, Kelowna, Canada V1V 1V7, Canada"}]}],"member":"219","published-online":{"date-parts":[[2012,4,13]]},"reference":[{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719796"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00146-8"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(96)00050-6"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80013-2"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1137\/0214065"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0017474"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.01.001"},{"key":"rf9","first-page":"277","volume":"166","author":"Fouquet J.-L.","journal-title":"Discrete Math."},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00220-4"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1090-5"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1137\/0221027"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796303044"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704441435"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2009.01.016"},{"key":"rf18","first-page":"275","volume":"61","author":"El Mallah E. S.","journal-title":"Cong. Numer."},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(98)00319-7"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1007\/11604686_9"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1016\/S1570-8667(03)00009-1"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(74)90063-X"},{"key":"rf24","doi-asserted-by":"publisher","DOI":"10.1137\/0214020"},{"key":"rf25","first-page":"247","volume":"69","author":"Yan J.-H.","journal-title":"Discrete Appl. Math."},{"key":"rf26","doi-asserted-by":"publisher","DOI":"10.1145\/322154.322157"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830912500085","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T17:53:42Z","timestamp":1565200422000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830912500085"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,3]]},"references-count":22,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2012,4,13]]},"published-print":{"date-parts":[[2012,3]]}},"alternative-id":["10.1142\/S1793830912500085"],"URL":"https:\/\/doi.org\/10.1142\/s1793830912500085","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,3]]}}}