{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T02:44:54Z","timestamp":1725763494211},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642450297"},{"type":"electronic","value":"9783642450303"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-45030-3_52","type":"book-chapter","created":{"date-parts":[[2013,12,11]],"date-time":"2013-12-11T21:32:52Z","timestamp":1386797572000},"page":"558-567","source":"Crossref","is-referenced-by-count":6,"title":["An O *(1.1939 n ) Time Algorithm for Minimum Weighted Dominating Induced Matching"],"prefix":"10.1007","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","reference":[{"key":"52_CR1","doi-asserted-by":"crossref","unstructured":"Bjorklund, A.: Determinant sums for undirected hamiltonicity. In: Annual Symposium on Foundations of Computer Science, FOCS 2010, pp. 173\u2013182 (2010)","DOI":"10.1109\/FOCS.2010.24"},{"key":"52_CR2","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Fourier meets m\u00f6bius: fast subset convolution. In: Annual Symposium on Foundations of Computer Science, STOC 2007, pp. 67\u201374 (2007)","DOI":"10.1145\/1250790.1250801"},{"key":"52_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"650","DOI":"10.1007\/978-3-642-12200-2_56","volume-title":"LATIN 2010: Theoretical Informatics","author":"A. Brandst\u00e4dt","year":"2010","unstructured":"Brandst\u00e4dt, A., Hundt, C., Nevries, R.: Efficient edge domination on hole-free graphs in polynomial time. In: L\u00f3pez-Ortiz, A. (ed.) LATIN 2010. LNCS, vol.\u00a06034, pp. 650\u2013661. Springer, Heidelberg (2010)"},{"key":"52_CR4","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.-S., Lee, D.-T. (eds.) ISAAC 2012. LNCS, vol.\u00a07676, pp. 267\u2013277. Springer, Heidelberg (2012)","DOI":"10.1007\/978-3-642-35261-4_30"},{"key":"52_CR5","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Mosca, R.: Dominating Induced Matchings for P\n                  7-free Graphs in Linear Time. In: Asano, T., Nakano, S.-I., Okamoto, Y., Watanabe, O. (eds.) ISAAC 2011. LNCS, vol.\u00a07074, pp. 100\u2013109. Springer, Heidelberg (2011)","DOI":"10.1007\/978-3-642-25591-5_12"},{"key":"52_CR6","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 Combinatoria\u00a067, 273\u2013281 (2003)","journal-title":"Ars Combinatoria"},{"key":"52_CR7","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/j.dam.2010.03.011","volume":"159","author":"D.M. 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 Applied Mathematics\u00a0159, 21\u2013531 (2011)","journal-title":"Discrete Applied Mathematics"},{"key":"52_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/978-3-642-02029-2_8","volume-title":"Graph Theory, Computational Intelligence and Thought","author":"D.M. Cardoso","year":"2009","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. LNCS, vol.\u00a05420, pp. 77\u201386. Springer, Heidelberg (2009)"},{"key":"52_CR9","doi-asserted-by":"publisher","first-page":"3060","DOI":"10.1016\/j.dam.2008.01.021","volume":"156","author":"D.M. Cardoso","year":"2008","unstructured":"Cardoso, D.M., Cerdeira, J.O., Delorme, C., Silva, P.C.: Efficient edge domination in regular graphs. Discrete Applied Mathematics\u00a0156, 3060\u20133065 (2008)","journal-title":"Discrete Applied Mathematics"},{"key":"52_CR10","doi-asserted-by":"publisher","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. Theoretical Computer Science\u00a0332, 265\u2013291 (2005)","journal-title":"Theoretical Computer Science"},{"key":"52_CR11","unstructured":"Dahll\u00f6f, V., Jonsson, P.: An algorithm for counting maximum weighted independent sets and its applications. In: ACM-SIAM Symposium on Discrete Algorithms, SODA 2002, pp. 292\u2013298 (2002)"},{"key":"52_CR12","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/s00453-007-9133-3","volume":"54","author":"F.V. Fomin","year":"2009","unstructured":"Fomin, F.V., Gaspers, S., Saurabh, S., Stepanov, A.A.: On two techniques of combining branching and treewidth. Algorithmica\u00a054, 181\u2013207 (2009)","journal-title":"Algorithmica"},{"key":"52_CR13","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Grandoni, F., Kratsch, D.: Measure and conquer: a simple O\n                  *(1.220\n                    n\n                  ) independent set algorithm. In: SODA 2006 ACM-SIAM Symposium on Discrete Algorithms, pp. 18\u201325 (2006)","DOI":"10.1145\/1109557.1109560"},{"key":"52_CR14","series-title":"EATCS Series in Theoretical Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16533-7","volume-title":"Exact Exponential Algorithms","author":"F.V. Fomin","year":"2010","unstructured":"Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. EATCS Series in Theoretical Computer Science. Springer, Berlin (2010)"},{"key":"52_CR15","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/0020-0190(93)90084-M","volume":"48","author":"D.L. Grinstead","year":"1993","unstructured":"Grinstead, D.L., Slater, P.J., Sherwani, N.A., Holmes, N.D.: Efficient edge domination problems in graphs. Information Processing Letters\u00a048, 221\u2013228 (1993)","journal-title":"Information Processing Letters"},{"key":"52_CR16","doi-asserted-by":"publisher","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 Journal on Discrete Mathematics\u00a026, 1758\u20131780 (2012)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"52_CR17","doi-asserted-by":"publisher","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. Electronic Notes in Discrete Mathematics\u00a032, 133\u2013140 (2009)","journal-title":"Electronic Notes in Discrete Mathematics"},{"key":"52_CR18","unstructured":"Lin, M.C., Mizrahi, M.J., Szwarcfiter, J.L.: Exact algorithms for dominating induced matchings. CoRR, abs\/1301.7602 (2013)"},{"key":"52_CR19","doi-asserted-by":"crossref","unstructured":"Livingston, M., Stout, Q.F.: Distributing resources in hypercube computers. In: C3P Proceedings of the Third Conference on Hypercube Concurrent Computers and Applications: Architecture, Software, Computer Systems, and General Issues, vol.\u00a01, pp. 222\u2013231. ACM (1988)","DOI":"10.1145\/62297.62324"},{"key":"52_CR20","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/S0166-218X(01)00198-6","volume":"119","author":"C.L. Lu","year":"2002","unstructured":"Lu, C.L., Ko, M.-T., Tang, C.Y.: Perfect edge domination and efficient edge domination in graphs. Discrete Applied Mathematics\u00a0119, 227\u2013250 (2002)","journal-title":"Discrete Applied Mathematics"},{"key":"52_CR21","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/S0166-218X(98)00057-2","volume":"87","author":"C.L. Lu","year":"1998","unstructured":"Lu, C.L., Tang, C.Y.: Solving the weighted efficient edge domination problem on bipartite permutation graphs. Discrete Applied Mathematics\u00a087, 203\u2013211 (1998)","journal-title":"Discrete Applied Mathematics"},{"key":"52_CR22","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1002\/jgt.21685","volume":"73","author":"M. Milanic","year":"2013","unstructured":"Milanic, M.: Hereditary efficiently dominatable graphs. Journal of Graph Theory\u00a073, 400\u2013424 (2013)","journal-title":"Journal of Graph Theory"},{"key":"52_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"554","DOI":"10.1007\/978-3-642-04128-0_50","volume-title":"Algorithms - ESA 2009","author":"J.M.M. Rooij van","year":"2009","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 2009. LNCS, vol.\u00a05757, pp. 554\u2013565. Springer, Heidelberg (2009)"},{"key":"52_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1007\/978-3-540-79723-4_19","volume-title":"Parameterized and Exact Computation","author":"M. Wahlstr\u00f6m","year":"2008","unstructured":"Wahlstr\u00f6m, M.: A tighter bound for counting max-weight solutions to 2SAT instances. In: Grohe, M., Niedermeier, R. (eds.) IWPEC 2008. LNCS, vol.\u00a05018, pp. 202\u2013213. Springer, Heidelberg (2008)"},{"key":"52_CR25","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/3-540-36478-1_17","volume-title":"Combinatorial Optimization - Eureka, you Shrink!","author":"G.J. Woeginger","year":"2003","unstructured":"Woeginger, G.J.: Exact algorithms for NP-hard problems: a survey. In: Combinatorial Optimization - Eureka, you Shrink!, pp. 185\u2013207. Springer-Verlag New York, Inc., New York (2003)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-45030-3_52","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,25]],"date-time":"2019-05-25T06:35:06Z","timestamp":1558766106000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-45030-3_52"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642450297","9783642450303"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-45030-3_52","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}