{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,7,29]],"date-time":"2022-07-29T07:56:07Z","timestamp":1659081367853},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2015,11,19]],"date-time":"2015-11-19T00:00:00Z","timestamp":1447891200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,3]]},"DOI":"10.1007\/s00453-015-0095-6","type":"journal-article","created":{"date-parts":[[2015,11,19]],"date-time":"2015-11-19T14:42:31Z","timestamp":1447944151000},"page":"642-660","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Exact Algorithms for Minimum Weighted Dominating Induced Matching"],"prefix":"10.1007","volume":"77","author":[{"given":"Min Chih","family":"Lin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michel J.","family":"Mizrahi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jayme L.","family":"Szwarcfiter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,11,19]]},"reference":[{"key":"95_CR1","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A.: Determinant sums for undirected hamiltonicity. In: Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pp. 173\u2013182 (Washington, DC, USA), FOCS \u201910, IEEE Computer Society (2010)","DOI":"10.1109\/FOCS.2010.24"},{"key":"95_CR2","volume-title":"Encyclopedia of Algorithms","author":"A Bj\u00f6rklund","year":"2008","unstructured":"Bj\u00f6rklund, A., Husfeldt, T.: Exact graph coloring using inclusion-exclusion. In: Kao, M.-Y. (ed.) Encyclopedia of Algorithms. Springer, Berlin (2008)"},{"key":"95_CR3","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Fourier meets mobius: fast subset convolution. In: Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing (New York, NY, USA), STOC \u201907, ACM, pp. 67\u201374 (2007)","DOI":"10.1145\/1250790.1250801"},{"key":"95_CR4","first-page":"3","volume":"10","author":"M Blank","year":"1973","unstructured":"Blank, M.: An estimate of the external stability of a graph without pendant vertices. Prikl. Math. Programmirovanie 10, 3\u201311 (1973)","journal-title":"Prikl. Math. Programmirovanie"},{"key":"95_CR5","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Hundt, C., Nevries, R.: Efficient edge domination on hole-free graphs in polynomial time. In: Proceedings of the 9th Latin American Conference on Theoretical Informatics, pp. 650\u2013661 (Berlin, Heidelberg), LATIN\u201910, Springer (2010)","DOI":"10.1007\/978-3-642-12200-2_56"},{"key":"95_CR6","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Leitert, A., Rautenbach, D.: Efficient dominating and edge dominating sets for graphs and hypergraphs. In: (Chao, K.-M., Hsu, T., Lee, D.-T. (eds.) ISAAC, Lecture Notes in Computer Science, vol. 7676, pp. 267\u2013277. Springer (2012)","DOI":"10.1007\/978-3-642-35261-4_30"},{"key":"95_CR7","first-page":"273","volume":"67","author":"A Brandst\u00e4dt","year":"2003","unstructured":"Brandst\u00e4dt, A., Lozin, V.V.: On the linear structure and clique-width of bipartite permutation graphs. Ars Comb. 67, 273\u2013281 (2003)","journal-title":"Ars Comb."},{"key":"95_CR8","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Mosca, R.: Dominating induced matchings for $$P_7$$ P 7 -free graphs in linear time. In: Asano, T., Nakano, S.-I., Okamoto, Y., Watanabe, O. (eds.) ISAAC, Lecture Notes in Computer Science, vol. 7074, pp. 100\u2013109. Springer (2011)","DOI":"10.1007\/978-3-642-25591-5_12"},{"issue":"7","key":"95_CR9","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1016\/j.dam.2010.03.011","volume":"159","author":"DM Cardoso","year":"2011","unstructured":"Cardoso, D.M., Korpelainen, N., Lozin, V.V.: On the complexity of the dominating induced matching problem in hereditary classes of graphs. Discrete Appl. Math. 159(7), 521\u2013531 (2011)","journal-title":"Discrete Appl. Math."},{"issue":"15","key":"95_CR10","doi-asserted-by":"crossref","first-page":"3060","DOI":"10.1016\/j.dam.2008.01.021","volume":"156","author":"DM Cardoso","year":"2008","unstructured":"Cardoso, D.M., Cerdeira, J.O., Delorme, C., Silva, P.C.: Efficient edge domination in regular graphs. Discrete Appl. Math. 156(15), 3060\u20133065 (2008)","journal-title":"Discrete Appl. Math."},{"key":"95_CR11","doi-asserted-by":"crossref","unstructured":"Cardoso, D.M., Lozin, V.V.: Dominating induced matchings. In: Lipshteyn, M., Levit, V.E., McConnell, R.M. (eds.) Graph Theory, Computational Intelligence and Thought , Lecture Notes in Computer Science, vol. 5420, pp. 77\u201386. Springer (2009)","DOI":"10.1007\/978-3-642-02029-2_8"},{"issue":"1","key":"95_CR12","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1145\/2071379.2071387","volume":"8","author":"M Cygan","year":"2012","unstructured":"Cygan, M., Pilipczuk, M.: Even faster exact bandwidth. ACM Trans. Algorithms 8(1), 8 (2012)","journal-title":"ACM Trans. Algorithms"},{"key":"95_CR13","first-page":"292","volume-title":"SODA","author":"V Dahll\u00f6f","year":"2002","unstructured":"Dahll\u00f6f, V., Jonsson, P.: An algorithm for counting maximum weighted independent sets and its applications. In: Eppstein, D. (ed.) SODA, pp. 292\u2013298. ACM\/SIAM, Philadelphia (2002)"},{"issue":"1\u20133","key":"95_CR14","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/j.tcs.2004.10.037","volume":"332","author":"V Dahll\u00f6f","year":"2005","unstructured":"Dahll\u00f6f, V., Jonsson, P., Wahlstr\u00f6m, M.: Counting models for 2SAT and 3SAT formulae. Theor. Comput. Sci. 332(1\u20133), 265\u2013291 (2005)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"95_CR15","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/s00453-007-9133-3","volume":"54","author":"FV Fomin","year":"2009","unstructured":"Fomin, F.V., Gaspers, S., Saurabh, S., Stepanov, A.A.: On two techniques of combining branching and treewidth. Algorithmica 54(2), 181\u2013207 (2009)","journal-title":"Algorithmica"},{"key":"95_CR16","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-16533-7","volume-title":"Exact Exponential Algorithms","author":"FV Fomin","year":"2010","unstructured":"Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Texts in Theoretical Computer Science. Springer, Berlin (2010)"},{"issue":"5","key":"95_CR17","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/0020-0190(93)90084-M","volume":"48","author":"DL Grinstead","year":"1993","unstructured":"Grinstead, D.L., Slater, P.J., Sherwani, N.A., Holmes, N.D.: Efficient edge domination problems in graphs. Inf. Process. Lett. 48(5), 221\u2013228 (1993)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"95_CR18","doi-asserted-by":"crossref","first-page":"1758","DOI":"10.1137\/09077850X","volume":"26","author":"S Gupta","year":"2012","unstructured":"Gupta, S., Raman, V., Saurabh, S.: Maximum r-regular induced subgraph problem: fast exponential algorithms and combinatorial bounds. SIAM J. Discrete Math. 26(4), 1758\u20131780 (2012)","journal-title":"SIAM J. Discrete Math."},{"key":"95_CR19","doi-asserted-by":"crossref","unstructured":"Iwata, Y.: A faster algorithm for dominating set analyzed by the potential method. In: Marx, D., Rossmanith, P. (eds.) Parameterized and Exact Computation\u20146th International Symposium, IPEC 2011, Saarbr\u00fccken, Germany, September 6\u20138, 2011. Revised Selected Papers, Lecture Notes in Computer Science, vol. 7112, pp. 41\u201354. Springer (2011)","DOI":"10.1007\/978-3-642-28050-4_4"},{"key":"95_CR20","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/j.endm.2009.02.018","volume":"32","author":"N Korpelainen","year":"2009","unstructured":"Korpelainen, N.: A polynomial-time algorithm for the dominating induced matching problem in the class of convex graphs. Electron. Notes Discrete Math. 32, 133\u2013140 (2009)","journal-title":"Electron. Notes Discrete Math."},{"key":"95_CR21","unstructured":"Lin, M.C., Mizrahi, M.J., Szwarcfiter, J.L.: Exact algorithms for dominating induced matchings. CoRR abs\/1301.7602 (2013)"},{"key":"95_CR22","doi-asserted-by":"crossref","unstructured":"Lin, M.C., Mizrahi, M.J., Szwarcfiter, J.L.: An O*(1.1939 n) time algorithm for minimum weighted dominating induced matching. In: Cai, L., Cheng, S.-W., Lam, T.W. (eds.) ISAAC, Lecture Notes in Computer Science, vol. 8283, pp. 558\u2013567. Springer (2013)","DOI":"10.1007\/978-3-642-45030-3_52"},{"key":"95_CR23","doi-asserted-by":"crossref","unstructured":"Livingston, M., Stout, Q.F.: Distributing resources in hypercube computers. In: Proceedings of the Third Conference on Hypercube Concurrent Computers and Applications: Architecture, Software, Computer Systems, and General Issues, vol. 1, pp. 222\u2013231 (New York, NY, USA), C3P, ACM (1988)","DOI":"10.1145\/62297.62324"},{"issue":"3","key":"95_CR24","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1016\/S0166-218X(01)00198-6","volume":"119","author":"CL Lu","year":"2002","unstructured":"Lu, C.L., Ko, M.-T., Tang, C.Y.: Perfect edge domination and efficient edge domination in graphs. Discrete Appl. Math. 119(3), 227\u2013250 (2002)","journal-title":"Discrete Appl. Math."},{"issue":"1\u20133","key":"95_CR25","first-page":"203","volume":"87","author":"CL Lu","year":"1998","unstructured":"Lu, C.L., Tang, C.Y.: Solving the weighted efficient edge domination problem on bipartite permutation graphs. Discrete Appl. Math. 87(1\u20133), 203\u2013211 (1998)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"95_CR26","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1002\/jgt.21685","volume":"73","author":"M Milanic","year":"2013","unstructured":"Milanic, M.: Hereditary efficiently dominatable graphs. J. Graph Theory 73(4), 400\u2013424 (2013)","journal-title":"J. Graph Theory"},{"key":"95_CR27","doi-asserted-by":"crossref","unstructured":"Ore, O.: Theory of graphs. Am. Math. Soc. Colloq. Publ. 38 (1962)","DOI":"10.1090\/coll\/038"},{"key":"95_CR28","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1017\/S0963548300002042","volume":"5","author":"BA Reed","year":"1996","unstructured":"Reed, B.A.: Paths, stars and the number three. Comb. Probab. Comput. 5, 277\u2013295 (1996)","journal-title":"Comb. Probab. Comput."},{"issue":"3","key":"95_CR29","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1137\/0206036","volume":"6","author":"S Tsukiyama","year":"1977","unstructured":"Tsukiyama, S., Ide, M., Ariyoshi, H., Shirakawa, I.: A new algorithm for generating all the maximal independent sets. SIAM J. Comput. 6(3), 505\u2013517 (1977)","journal-title":"SIAM J. Comput."},{"key":"95_CR30","doi-asserted-by":"crossref","unstructured":"van Rooij, J.M.M., Nederlof, J., van Dijk, T.C.: Inclusion\/exclusion meets measure and conquer. In: Fiat, A., Sanders, P. (eds.) ESA, Lecture Notes in Computer Science, vol. 5757, pp. 554\u2013565. Springer (2009)","DOI":"10.1007\/978-3-642-04128-0_50"},{"key":"95_CR31","doi-asserted-by":"crossref","unstructured":"Wahlstr\u00f6m, M.: A tighter bound for counting max-weight solutions to 2sat instances. In: Proceedings of the 3rd International Conference on Parameterized and Exact Computation, pp. 202\u2013213 (Berlin, Heidelberg). IWPEC\u201908, Springer (2008)","DOI":"10.1007\/978-3-540-79723-4_19"},{"key":"95_CR32","volume-title":"Woeginger, Combinatorial optimization\u2013Eureka, You Shrink!","author":"J Gerhard","year":"2003","unstructured":"Gerhard, J.: Woeginger, Combinatorial optimization\u2013Eureka, You Shrink!. Springer-Verlag New York Inc., New York (2003)"},{"key":"95_CR33","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/j.dam.2015.04.012","volume":"190\u2013191","author":"M Xiao","year":"2015","unstructured":"Xiao, M., Nagamochi, H.: Exact algorithms for dominating induced matching based on graph partition. Discrete Appl. Math. 190\u2013191, 147\u2013162 (2015)","journal-title":"Discrete Appl. Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0095-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-0095-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0095-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0095-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,1]],"date-time":"2019-09-01T18:14:20Z","timestamp":1567361660000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-0095-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,11,19]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,3]]}},"alternative-id":["95"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-0095-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,11,19]]}}}