{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,15]],"date-time":"2026-02-15T03:27:48Z","timestamp":1771126068706,"version":"3.50.1"},"reference-count":77,"publisher":"Elsevier BV","issue":"1-3","license":[{"start":{"date-parts":[[1999,1,1]],"date-time":"1999-01-01T00:00:00Z","timestamp":915148800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":5311,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Applied Mathematics"],"published-print":{"date-parts":[[1999,1]]},"DOI":"10.1016\/s0166-218x(98)00147-4","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T08:12:16Z","timestamp":1027584736000},"page":"155-175","source":"Crossref","is-referenced-by-count":36,"title":["On the algorithmic complexity of twelve covering and independence parameters of graphs"],"prefix":"10.1016","volume":"91","author":[{"given":"David F.","family":"Manlove","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0166-218X(98)00147-4_BIB1","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1002\/jgt.3190010209","article-title":"Total matchings and total coverings of graphs","volume":"1","author":"Alavi","year":"1977","journal-title":"J. Graph Theory"},{"key":"10.1016\/S0166-218X(98)00147-4_BIB2","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/0012-365X(92)90643-T","article-title":"On total covers of graphs","volume":"100","author":"Alavi","year":"1992","journal-title":"Discrete Math."},{"issue":"1","key":"10.1016\/S0166-218X(98)00147-4_BIB3","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1145\/174644.174650","article-title":"Approximation algorithms for NP-complete problems on planar graphs","volume":"41","author":"Baker","year":"1994","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/S0166-218X(98)00147-4_BIB4","series-title":"Graphs and Hypergraphs","author":"Berge","year":"1973"},{"key":"10.1016\/S0166-218X(98)00147-4_BIB5","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/0020-0190(84)90126-1","article-title":"Dominating sets for split and bipartite graphs","volume":"19","author":"Bertossi","year":"1984","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0166-218X(98)00147-4_BIB6","series-title":"Proceedings of the 8th South-Eastern Conf. on Combinatorics, Graph Theory and Computing, Utilitas Mathematica","first-page":"321","article-title":"Independent domination in trees","author":"Beyer","year":"1997"},{"issue":"1","key":"10.1016\/S0166-218X(98)00147-4_BIB7","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1137\/0211015","article-title":"Dominating sets in chordal graphs","volume":"11","author":"Booth","year":"1982","journal-title":"SIAM J. Comput."},{"issue":"1\u20133","key":"10.1016\/S0166-218X(98)00147-4_BIB8","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/S0166-218X(97)00125-X","article-title":"The algorithmic use of hypertree structure and maximum neighbourhood orderings","volume":"82","author":"Brandst\u00e4dt","year":"1998","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0166-218X(98)00147-4_BIB9","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/0304-3975(87)90128-9","article-title":"On domination problems for permutation and other graphs","volume":"54","author":"Brandst\u00e4dt","year":"1987","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0166-218X(98)00147-4_BIB10","series-title":"Proceedings of the 24th International Colloquium on Automata, Languages and Programming","first-page":"760","article-title":"Independent sets in asteriodal triple-free graphs","volume":"vol. 1256","author":"Broersma","year":"1997"},{"issue":"6","key":"10.1016\/S0166-218X(98)00147-4_BIB11","doi-asserted-by":"crossref","first-page":"1671","DOI":"10.1137\/S0097539792238431","article-title":"Efficient algorithms for the domination problems on interval and circular-arc graphs","volume":"27","author":"Chang","year":"1998","journal-title":"SIAM J. Comput."},{"issue":"2","key":"10.1016\/S0166-218X(98)00147-4_BIB12","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1111\/j.2164-0947.1974.tb01571.x","article-title":"On the independence numbers of complementary graphs","volume":"36","author":"Chartrand","year":"1974","journal-title":"Trans. New York Aead. Sci."},{"key":"10.1016\/S0166-218X(98)00147-4_BIB13","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1002\/net.3230100304","article-title":"Total domination in graphs","volume":"10","author":"Cockayne","year":"1980","journal-title":"Networks"},{"key":"10.1016\/S0166-218X(98)00147-4_BIB14","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1016\/0012-365X(91)90151-Q","article-title":"The product of the independent domination numbers of a graph and its complement","volume":"90","author":"Cockayne","year":"1991","journal-title":"Discrete Math."},{"key":"10.1016\/S0166-218X(98)00147-4_BIB15","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/0012-365X(94)00202-T","article-title":"On a Nordhaus-Gaddum type problem for independent domination","volume":"138","author":"Cockayne","year":"1995","journal-title":"Discrete Math."},{"key":"10.1016\/S0166-218X(98)00147-4_BIB16","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/0020-0190(75)90011-3","article-title":"A linear algorithm for the domination number of a tree","volume":"4","author":"Cockayne","year":"1975","journal-title":"Inform. Proces. Lett."},{"key":"10.1016\/S0166-218X(98)00147-4_BIB17","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/0012-365X(88)90192-6","article-title":"Gallai theorems for graphs, hypergraphs and set systems","volume":"72","author":"Cockayne","year":"1988","journal-title":"Discrete Math."},{"key":"10.1016\/S0166-218X(98)00147-4_BIB18","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/0012-365X(89)90304-X","article-title":"On the product of upper irredundancc numbers of a graph and its complement","volume":"76","author":"Cockayne","year":"1989","journal-title":"Discrete Math."},{"issue":"1","key":"10.1016\/S0166-218X(98)00147-4_BIB19","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/0166-218X(84)90088-X","article-title":"Clustering and domination in perfect graphs","volume":"9","author":"Corneil","year":"1984","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0166-218X(98)00147-4_BIB20","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/0012-365X(90)90357-N","article-title":"Dominating sets in perfect graphs","volume":"86","author":"Corneil","year":"1990","journal-title":"Discrete Math."},{"key":"10.1016\/S0166-218X(98)00147-4_BIB21","article-title":"A compendium of NP optimization problems","author":"Crcscenzi","year":"1995"},{"key":"10.1016\/S0166-218X(98)00147-4_BIB22","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1017\/S1446788700004031","article-title":"Algorithms for generalized stability numbers of tree graphs","volume":"6","author":"Daykin","year":"1966","journal-title":"J. Australasian Math. Soc."},{"key":"10.1016\/S0166-218X(98)00147-4_BIB23","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1016\/0196-6774(86)90002-7","article-title":"Planar 3DM is NP-complete","volume":"7","author":"Dyer","year":"1986","journal-title":"J. Algorithms"},{"key":"10.1016\/S0166-218X(98)00147-4_BIB24","doi-asserted-by":"crossref","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","article-title":"Paths, trees and flowers","volume":"17","author":"Edmonds","year":"1965","journal-title":"Can. J. Math."},{"key":"10.1016\/S0166-218X(98)00147-4_BIB25","first-page":"63","article-title":"Domination in polygon graphs","volume":"77","author":"Elmallah","year":"1990"},{"key":"10.1016\/S0166-218X(98)00147-4_BIB26","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/0012-365X(77)90102-9","article-title":"On total matching numbers and total covering numbers of complementary graphs","volume":"19","author":"Erd\u00f6s","year":"1977","journal-title":"Discrete Math."},{"key":"10.1016\/S0166-218X(98)00147-4_BIB27","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1016\/0167-6377(82)90015-3","article-title":"Independent domination in chordal graphs","volume":"1","author":"Farber","year":"1982","journal-title":"Oper. Res. Lett."},{"issue":"2","key":"10.1016\/S0166-218X(98)00147-4_BIB28","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/0166-218X(84)90061-1","article-title":"Domination, independent domination and duality in strongly chordal graphs","volume":"7","author":"Farber","year":"1984","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"10.1016\/S0166-218X(98)00147-4_BIB29","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0196-6774(85)90001-X","article-title":"Domination in permutation graphs","volume":"6","author":"Farber","year":"1985","journal-title":"J. Algorithms"},{"key":"10.1016\/S0166-218X(98)00147-4_BIB30","first-page":"133","article-title":"\u00dcber extreme Punkt-und Kantenmengen","volume":"2","author":"Gallai","year":"1959","journal-title":"Ann. Univ. Sci. Budapest E\u00f6tv\u00f6s Sect. Math."},{"issue":"4","key":"10.1016\/S0166-218X(98)00147-4_BIB31","doi-asserted-by":"crossref","first-page":"826","DOI":"10.1137\/0132071","article-title":"The rectilinear Steiner tree problem is NP-complete","volume":"32","author":"Garey","year":"1977","journal-title":"SIAM J. Appl. Math."},{"key":"10.1016\/S0166-218X(98)00147-4_BIB32","unstructured":"M.R. Garey, D.S. Johnson, unpublished result, 1978."},{"key":"10.1016\/S0166-218X(98)00147-4_BIB33","series-title":"Computers and Intractability","author":"Garey","year":"1979"},{"key":"10.1016\/S0166-218X(98)00147-4_BIB34","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","article-title":"Some simplified NP-complete graph problems","volume":"1","author":"Garey","year":"1976","journal-title":"Theoret, Comput, Sci."},{"key":"10.1016\/S0166-218X(98)00147-4_BIB35","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1137\/0201013","article-title":"Algorithms for minimum coloring, maximum clique, Minimum covering by eliques, and Maximum independent set of a chordal graph","volume":"1","author":"Gavril","year":"1972","journal-title":"SIAM, J. Comput."},{"key":"10.1016\/S0166-218X(98)00147-4_BIB36_1","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/S0012-365X(96)00181-1","article-title":"Double total domination of graphs","volume":"165","author":"Gimbel","year":"1997","journal-title":"Discrete Math."},{"key":"10.1016\/S0166-218X(98)00147-4_BIB36_2","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/S0012-365X(96)00181-1","article-title":"Double total domination of graphs","volume":"166","author":"Gimbel","year":"1997","journal-title":"Discrete Math."},{"key":"10.1016\/S0166-218X(98)00147-4_BIB37","first-page":"109","article-title":"Inequalities for total matchings of graphs","volume":"39","author":"Gimbel","year":"1995","journal-title":"Ars Combin."},{"key":"10.1016\/S0166-218X(98)00147-4_BIB38","series-title":"Algorithmic Graph Theory and Perfect Graphs","author":"Golumbic","year":"1980"},{"key":"10.1016\/S0166-218X(98)00147-4_BIB39","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/0166-218X(94)90020-5","article-title":"A recurrence template for several parameters in series-parallel graphs","volume":"54","author":"Grinstead","year":"1994","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0166-218X(98)00147-4_BIB40","series-title":"Proof Techniques in Graph Theory","first-page":"61","article-title":"Independence and covering numbers of line graphs and Total Graphs","author":"Gupta","year":"1969"},{"key":"10.1016\/S0166-218X(98)00147-4_BIB41","series-title":"Graph Theory","author":"Harary","year":"1969"},{"key":"10.1016\/S0166-218X(98)00147-4_BIB42","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0012-365X(94)00373-Q","article-title":"Nordhaus-Gaddum inequalities for domination in graphs","volume":"155","author":"Harary","year":"1996","journal-title":"Discrete Math."},{"key":"10.1016\/S0166-218X(98)00147-4_BIB43","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1016\/0012-365X(94)00022-B","article-title":"independent domination in regular graphs","volume":"143","author":"Haviland","year":"1995","journal-title":"Discrete Math."},{"key":"10.1016\/S0166-218X(98)00147-4_BIB44","series-title":"Domination in Graphs: Advanced Topics","year":"1998"},{"key":"10.1016\/S0166-218X(98)00147-4_BIB45","series-title":"Fundamentals of Domination in Graphs","author":"Haynes","year":"1998"},{"key":"10.1016\/S0166-218X(98)00147-4_BIB46","first-page":"671","article-title":"Domination, independence and irredundance in total graphs: a brief survey","volume":"vol. 2","author":"Hedetniemi","year":"1995"},{"key":"10.1016\/S0166-218X(98)00147-4_BIB47","first-page":"23","article-title":"A max-min relationship between matchings and domination in graphs","volume":"40","author":"Hedetniemi","year":"1983"},{"key":"10.1016\/S0166-218X(98)00147-4_BIB48","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1137\/0406030","article-title":"Minimum edge dominating sets","volume":"6","author":"Horton","year":"1993","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/S0166-218X(98)00147-4_BIB49","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/0020-0190(91)90188-N","article-title":"On approximating the minimum independent dominating set","volume":"37","author":"Irving","year":"1991","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0166-218X(98)00147-4_BIB50","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/0012-365X(90)90349-M","article-title":"Chordal graphs and upper irredundance, Upper domination and Independence","volume":"86","author":"Jacobson","year":"1990","journal-title":"Discrete Math."},{"key":"10.1016\/S0166-218X(98)00147-4_BIB51","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/0196-6774(84)90045-2","article-title":"The NP-completeness column: an ongoing guide","volume":"5","author":"Johnson","year":"1984","journal-title":"J. Algorithms"},{"key":"10.1016\/S0166-218X(98)00147-4_BIB52","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1016\/0196-6774(85)90012-4","article-title":"The NP-completeness column: an ongoing guide","volume":"6","author":"Johnson","year":"1985","journal-title":"J. Algorithms"},{"issue":"6","key":"10.1016\/S0166-218X(98)00147-4_BIB53","first-page":"443","article-title":"The NP-completeness of the dominating set problem in cubic planar graphs","volume":"E 63","author":"Kikuno","year":"1980","journal-title":"Trans. Inst. Electron. Commun. Engrs Japan"},{"key":"10.1016\/S0166-218X(98)00147-4_BIB54","first-page":"65","article-title":"An analysis of the greedy heuristic for independence systems","volume":"vol. 2","author":"Korte","year":"1978"},{"key":"10.1016\/S0166-218X(98)00147-4_BIB55","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1137\/0406032","article-title":"Domination on cocomparability graphs","volume":"6","author":"Kratsch","year":"1993","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/S0166-218X(98)00147-4_BIB56","series-title":"Advances in Graph Theory","first-page":"237","article-title":"Entire domination in graphs","author":"Kulli","year":"1991"},{"key":"10.1016\/S0166-218X(98)00147-4_BIB57","article-title":"Matching Theory","volume":"vol. 29","author":"Lov\u00e1sz","year":"1986"},{"key":"10.1016\/S0166-218X(98)00147-4_BIB58","article-title":"A note on the complexity of the superstring problem","volume":"233","author":"Maier","year":"1977"},{"key":"10.1016\/S0166-218X(98)00147-4_BIB59","article-title":"Neighborhood hypergraphs: a framework for covering and packing parameters in a graph","author":"Majumdar","year":"1992"},{"key":"10.1016\/S0166-218X(98)00147-4_BIB60","first-page":"639","article-title":"Strong independence in graphs","volume":"29","author":"McFall","year":"1980"},{"key":"10.1016\/S0166-218X(98)00147-4_BIB61","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1016\/0095-8956(78)90017-5","article-title":"On total covering and matching of graphs","volume":"24","author":"Meir","year":"1978","journal-title":"J. Combin. Theory Ser. B"},{"key":"10.1016\/S0166-218X(98)00147-4_BIB62","series-title":"Proceedings of the 8th South-Eastern Conference on Combinatorics, Graph Theory and Computing, Utilitas Mathematica","first-page":"489","article-title":"Edge domination in trees","author":"Mitchell","year":"1977"},{"key":"10.1016\/S0166-218X(98)00147-4_BIB63","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1093\/imamat\/14.2.183","article-title":"Two bounds for the domination number of a graph","volume":"14","author":"Nieminen","year":"1974","journal-title":"J. Inst. Math. Appl."},{"key":"10.1016\/S0166-218X(98)00147-4_BIB64","series-title":"Proceedings of the International Conference on the Theory and Applications of Graphs","first-page":"420","article-title":"Generalizations of graphical parameters","volume":"vol. 642","author":"Nordhaus","year":"1976"},{"key":"10.1016\/S0166-218X(98)00147-4_BIB65","doi-asserted-by":"crossref","first-page":"175","DOI":"10.2307\/2306658","article-title":"On complementary graphs","volume":"63","author":"Nordhaus","year":"1956","journal-title":"Amer. Math. Mon."},{"key":"10.1016\/S0166-218X(98)00147-4_BIB66","first-page":"315","article-title":"An algorithm for a minimum cover of a graph","volume":"10","author":"Norman","year":"1959"},{"key":"10.1016\/S0166-218X(98)00147-4_BIB67","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/0166-218X(94)90216-X","article-title":"Total matchings and total coverings of threshold graphs","volume":"49","author":"Peled","year":"1994","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0166-218X(98)00147-4_BIB68","first-page":"71","article-title":"Linear algorithms for independent domination and total domination in series-parallel graphs","volume":"45","author":"Pfaff","year":"1984"},{"key":"10.1016\/S0166-218X(98)00147-4_BIB69","series-title":"Domination in Graphs \u2014 Advanced Topics","first-page":"1","article-title":"Complementarity and generality of graphical subset parameters","author":"Slater","year":"1998"},{"issue":"3","key":"10.1016\/S0166-218X(98)00147-4_BIB70","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0020-0190(95)94093-8","article-title":"Edge domination on bipartite permutation graphs and cotriangulated graphs","volume":"56","author":"Srinivasan","year":"1995","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0166-218X(98)00147-4_BIB71","doi-asserted-by":"crossref","unstructured":"J.A. Telle, A. Proskurowski, Practical algorithms on partial K-trees with an application to domination-type problems, Proceedings of the 3rd Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science, vol. 709, Springer, Berlin, pp. 610\u2013621.","DOI":"10.1007\/3-540-57155-8_284"},{"key":"10.1016\/S0166-218X(98)00147-4_BIB72","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/0012-365X(93)90553-6","article-title":"Graphs with unique minimum edge dominating sets and graphs with unique maximum independent sets of vertices","volume":"121","author":"Topp","year":"1993","journal-title":"Discrete Math."},{"key":"10.1016\/S0166-218X(98)00147-4_BIB73","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/S0012-365X(96)00062-3","article-title":"Totally equimatchable graphs","volume":"164","author":"Topp","year":"1997","journal-title":"Discrete Math."},{"issue":"1","key":"10.1016\/S0166-218X(98)00147-4_BIB74","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1137\/0138030","article-title":"Edge Dominating sets in graphs","volume":"18","author":"Yannakakis","year":"1980","journal-title":"SIAM J. Appl. Math."},{"issue":"5","key":"10.1016\/S0166-218X(98)00147-4_BIB75","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1007\/BF02977883","article-title":"On the relations of graph parameters","volume":"36","author":"Zhang","year":"1991","journal-title":"Chinese Sci. Bull."},{"key":"10.1016\/S0166-218X(98)00147-4_BIB76","unstructured":"M. Zito, personal communication, 1997."}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X98001474?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X98001474?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T05:03:40Z","timestamp":1578459820000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0166218X98001474"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999,1]]},"references-count":77,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[1999,1]]}},"alternative-id":["S0166218X98001474"],"URL":"https:\/\/doi.org\/10.1016\/s0166-218x(98)00147-4","relation":{},"ISSN":["0166-218X"],"issn-type":[{"value":"0166-218X","type":"print"}],"subject":[],"published":{"date-parts":[[1999,1]]}}}