{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T23:56:25Z","timestamp":1742946985384,"version":"3.40.3"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319037790"},{"type":"electronic","value":"9783319037806"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-319-03780-6_16","type":"book-chapter","created":{"date-parts":[[2013,11,21]],"date-time":"2013-11-21T01:13:18Z","timestamp":1384996398000},"page":"178-189","source":"Crossref","is-referenced-by-count":2,"title":["On Complexities of Minus Domination"],"prefix":"10.1007","author":[{"given":"Lu\u00e9rbio","family":"Faria","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wing-Kai","family":"Hon","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ton","family":"Kloks","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hsiang-Hsuan","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tao-Ming","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yue-Li","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"16_CR1","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/s00453-001-0116-5","volume":"33","author":"J. Alber","year":"2002","unstructured":"Alber, J., Bodlaender, H., Fernau, H., Kloks, T., Niedermeier, R.: Fixed-parameter algorithms for dominating set and related problems on planar graphs. Algorithmica\u00a033, 461\u2013493 (2002)","journal-title":"Algorithmica"},{"key":"16_CR2","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1007\/s00453-008-9204-0","volume":"54","author":"N. Alon","year":"2009","unstructured":"Alon, N., Gutner, S.: Linear time algorithms for finding a dominating set of fixed size in degenerated graphs. Algorithmica\u00a054, 544\u2013556 (2009)","journal-title":"Algorithmica"},{"key":"16_CR3","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/S0166-218X(00)00219-5","volume":"108","author":"P. Damaschke","year":"2001","unstructured":"Damaschke, P.: Minus domination in small-degree graphs. Discrete Applied Mathematics\u00a0108, 53\u201364 (2001)","journal-title":"Discrete Applied Mathematics"},{"key":"16_CR4","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1145\/1077464.1077468","volume":"1","author":"E. Demaine","year":"2005","unstructured":"Demaine, E., Formin, F., Hajiaghayi, M., Thilikos, D.: Fixed-parameter algorithms for (k, r)-center in planar graphs and map graphs. ACM Transactions on Algorithms\u00a01, 33\u201347 (2005)","journal-title":"ACM Transactions on Algorithms"},{"key":"16_CR5","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/0166-218X(95)00056-W","volume":"68","author":"J. Dunbar","year":"1996","unstructured":"Dunbar, J., Goddard, W., Hedetniemi, S., Henning, M., McRae, A.: The algorithmic complexity of minus domination in graphs. Discrete Applied Mathematics\u00a068, 73\u201384 (1996)","journal-title":"Discrete Applied Mathematics"},{"key":"16_CR6","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/0166-218X(84)90061-1","volume":"7","author":"M. Farber","year":"1984","unstructured":"Farber, M.: Domination, independent domination, and duality in strongly chordal graphs. Discrete Applied Mathematics\u00a07, 115\u2013130 (1984)","journal-title":"Discrete Applied Mathematics"},{"key":"16_CR7","unstructured":"Fomin, F., Lokshtanov, D., Saurabh, S., Thilikos, D.: Linear kernels for (connected) dominating set on graphs with excluded topological subgraphs. In: Proceedings STACS 2013, Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik. LPIcs, vol.\u00a020, pp. 92\u2013103 (2013)"},{"key":"16_CR8","unstructured":"Frank, A.: Some polynomial algorithms for certain graphs and hypergraphs. In: Nash-Williams, C., Sheehan, J. (eds.) Proceedings 5th British Combinatorial Conference 1975. Congressus Numeratium XV, pp. 211\u2013226 (1975)"},{"key":"16_CR9","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1007\/BFb0121244","volume":"1","author":"D. Fulkerson","year":"1974","unstructured":"Fulkerson, D., Hoffman, A., Oppenheim, R.: On balanced matrices. Mathematical Programming Study\u00a01, 120\u2013132 (1974)","journal-title":"Mathematical Programming Study"},{"key":"16_CR10","first-page":"101","volume":"12","author":"J. Hattingh","year":"1995","unstructured":"Hattingh, J., Henning, M., Slater, P.: The algorithmic complexity of signed domination in graphs. Australasian Journal of Combinatorics\u00a012, 101\u2013112 (1995)","journal-title":"Australasian Journal of Combinatorics"},{"key":"16_CR11","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1137\/0606070","volume":"6","author":"A. Hoffman","year":"1985","unstructured":"Hoffman, A., Kolen, A., Sakarovitch, M.: Totally-balanced and greedy matrices. SIAM Journal on Algebraic and Discrete Methods\u00a06, 721\u2013730 (1985)","journal-title":"SIAM Journal on Algebraic and Discrete Methods"},{"key":"16_CR12","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1093\/qmath\/28.4.417","volume":"28","author":"E. Howorka","year":"1977","unstructured":"Howorka, E.: A characterization of distance-hereditary graphs. The Quarterly Journal of Mathematics\u00a028, 417\u2013420 (1977)","journal-title":"The Quarterly Journal of Mathematics"},{"key":"16_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth \u2013 Computations and Approximations","author":"T. Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth. LNCS, vol.\u00a0842. Springer, Heidelberg (1994)"},{"key":"16_CR14","unstructured":"Kloks, T., Liu, C., Poon, S.: Feedback vertex set on chordal bipartite graphs. Manuscript on arXiv: 1104.3915 (2012)"},{"key":"16_CR15","unstructured":"Kloks, T., Wang, Y.: Advances in graph algorithms (2013) (manuscript)"},{"key":"16_CR16","unstructured":"Kolen, A.: Location problems on trees and in the rectilinear plane, PhD Thesis, Mathematisch centrum, Amsterdam (1982)"},{"key":"16_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1007\/978-3-642-20877-5_49","volume-title":"Theory and Applications of Models of Computation","author":"A. Langer","year":"2011","unstructured":"Langer, A., Rossmanith, P., Sikdar, S.: Linear-time algorithms for graphs of bounded rankwidth: A fresh look using game theory. In: Ogihara, M., Tarui, J. (eds.) TAMC 2011. LNCS, vol.\u00a06648, pp. 505\u2013516. Springer, Heidelberg (2011)"},{"key":"16_CR18","doi-asserted-by":"publisher","first-page":"4185","DOI":"10.1016\/j.disc.2007.08.080","volume":"308","author":"C. Lee","year":"2008","unstructured":"Lee, C., Chang, M.: Variations of Y-dominating functions on graphs. Discrete Mathematics\u00a0308, 4185\u20134204 (2008)","journal-title":"Discrete Mathematics"},{"key":"16_CR19","unstructured":"Liang, H.: Signed and minus domination in complete multipartite graphs. Manuscript on arXiv: 1205.0343 (2012)"},{"key":"16_CR20","unstructured":"Lubiw, A.: \u0393-Free matrices, Master\u2019s Thesis, University of Waterloo, Canada (1982)"},{"key":"16_CR21","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1016\/S0012-365X(00)00252-1","volume":"233","author":"J. Matou\u0161ek","year":"2001","unstructured":"Matou\u0161ek, J.: Lower bound on the minus-domination number. Discrete Mathematics\u00a0233, 361\u2013370 (2001)","journal-title":"Discrete Mathematics"},{"key":"16_CR22","doi-asserted-by":"crossref","unstructured":"Mellor, A., Prieto, E., Mathieson, L., Moscato, P.: A kernelisation approach for multiple d-hitting set and its application in optimal multi-drug therapeutic combinations. PLoS One\u00a05, e13055 (2010)","DOI":"10.1371\/journal.pone.0013055"},{"key":"16_CR23","unstructured":"Scheinerman, E., Ullman, D.: Fractional graph theory. Wiley (1997)"},{"key":"16_CR24","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1006\/jctb.2000.2013","volume":"81","author":"A. Thomason","year":"2001","unstructured":"Thomason, A.: The extremal function for complete minors. Journal of Combinatorial Theory, Series B\u00a081, 318\u2013338 (2001)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"16_CR25","doi-asserted-by":"crossref","first-page":"343","DOI":"10.11650\/twjm\/1500405694","volume":"1","author":"H. Yeh","year":"1997","unstructured":"Yeh, H., Chang, G.: Algorithmic aspects of majority domination. Taiwanese Journal of Mathematics\u00a01, 343\u2013350 (1997)","journal-title":"Taiwanese Journal of Mathematics"},{"key":"16_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/978-3-642-38756-2_27","volume-title":"Frontiers in Algorithmics and Algorithmic Aspects in Information and Management","author":"Y. Zheng","year":"2013","unstructured":"Zheng, Y., Wang, J., Feng, Q.: Kernelization and lowerbounds of the signed domination problem. In: Fellows, M., Tan, X., Zhu, B. (eds.) FAW-AAIM 2013. LNCS, vol.\u00a07924, pp. 261\u2013271. Springer, Heidelberg (2013)"},{"key":"16_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"572","DOI":"10.1007\/978-3-642-29952-0_53","volume-title":"Theory and Applications of Models of Computation","author":"Y. Zheng","year":"2012","unstructured":"Zheng, Y., Wang, J., Feng, Q., Chen, J.: FPT results for signed domination. In: Agrawal, M., Cooper, S.B., Li, A. (eds.) TAMC 2012. LNCS, vol.\u00a07287, pp. 572\u2013583. Springer, Heidelberg (2012)"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-03780-6_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T09:03:13Z","timestamp":1558688593000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-03780-6_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783319037790","9783319037806"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-03780-6_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}