{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T06:13:12Z","timestamp":1725516792394},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540697329"},{"type":"electronic","value":"9783540697336"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-69733-6_21","type":"book-chapter","created":{"date-parts":[[2008,8,12]],"date-time":"2008-08-12T12:07:43Z","timestamp":1218542863000},"page":"204-214","source":"Crossref","is-referenced-by-count":0,"title":["Approximating Alternative Solutions"],"prefix":"10.1007","author":[{"given":"Michael","family":"Kr\u00fcger","sequence":"first","affiliation":[]},{"given":"Harald","family":"Hempel","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"21_CR1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-58412-1","volume-title":"Complexity and Approximation","author":"G. Ausiello","year":"1999","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation. Springer, Berlin (1999)"},{"issue":"1","key":"21_CR2","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/S0004-3702(98)00043-5","volume":"102","author":"A.M. Abdelbar","year":"1998","unstructured":"Abdelbar, A.M., Hedetniemi, S.M.: Approximating MAPs for Belief Networks is NP-hard and other Theorems. Artificial Intelligence\u00a0102(1), 21\u201338 (1998)","journal-title":"Artificial Intelligence"},{"issue":"4","key":"21_CR3","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0020-0190(89)90039-2","volume":"32","author":"M. Bern","year":"1989","unstructured":"Bern, M., Plassmann, P.: The Steiner Problem with Edge Lengths 1 and 2. Inform. Process. Lett.\u00a032(4), 171\u2013176 (1989)","journal-title":"Inform. Process. Lett."},{"issue":"1","key":"21_CR4","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1006\/jagm.1998.0998","volume":"31","author":"C. Bazgan","year":"1999","unstructured":"Bazgan, C., Santha, M., Tuza, Z.: On the Approximation of Finding another Hamiltonian Cycle in Cubic Hamiltonian Graphs. Journal of Algorithms\u00a031(1), 249\u2013268 (1999)","journal-title":"Journal of Algorithms"},{"key":"21_CR5","unstructured":"de Bondt, M.: On the ASP-Completeness of Cryptarisms. Technical Report 0419, Department of Mathematics, Radboud University of Nijmegen (2004)"},{"issue":"6","key":"21_CR6","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M.X. Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. J. Assoc. Comput. Mach.\u00a042(6), 1115\u20131145 (1995)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"4","key":"21_CR7","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0020-0190(93)90022-2","volume":"46","author":"M.M. Halld\u00f3rsson","year":"1993","unstructured":"Halld\u00f3rsson, M.M.: Approximating the Minimum Maximal Independence Number. Inform. Process. Lett.\u00a046(4), 169\u2013172 (1993)","journal-title":"Inform. Process. Lett."},{"issue":"3","key":"21_CR8","first-page":"317","volume":"1","author":"V. Kann","year":"1994","unstructured":"Kann, V.: Polynomially Bounded Minimization Problems that are Hard to Approximate. Nordic J. Comput. 1(3), 317\u2013331 (1994); Selected papers of the 20th International Colloquium on Automata, Languages and Programming (ICALP 1993), Lund (1993)","journal-title":"Nordic J. Comput."},{"key":"21_CR9","unstructured":"Kr\u00fcger, M.: Weitere Hamiltonkreise in Graphen und Inverse Hamiltonkreisprobleme (German). Master\u2019s thesis, Friedrich-Schiller-University Jena, Germany (2005)"},{"key":"21_CR10","unstructured":"Kr\u00fcger, M.: On the Complexity of Alternative Solutions. PhD Thesis, Friedrich-Schiller-University Jena, Germany (2008)"},{"key":"21_CR11","unstructured":"McPhail, B.P.: The Complexity of Puzzles: NP-Completeness Results for Nurikabe and Minesweeper. Bachelor thesis, The Division of Mathematics and Natural Sciences, Reed College, Portland (2003)"},{"key":"21_CR12","unstructured":"Orponen, P., Manila, H.: On Approximation Preserving Reductions: Complete Problems and Robust Measures (1990)"},{"key":"21_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/800113.803625","volume-title":"Proc. of Eighth Annual ACM Symposium on Theory of Computing","author":"C.H. Papadimitriou","year":"1976","unstructured":"Papadimitriou, C.H., Steiglitz, K.: Some Complexity Results for the Traveling Salesman Problem. In: Proc. of Eighth Annual ACM Symposium on Theory of Computing, Hershey, Pennsylvania,US, pp. 1\u20139. Assoc. Comput. Mach., New York (1976)"},{"key":"21_CR14","volume-title":"Combinatorial Optimization: Algorithms and Complexity","author":"C.H. Papadimitriou","year":"1982","unstructured":"Papadimitriou, C.H., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall Inc., Englewood Cliffs (1982)"},{"issue":"3","key":"21_CR15","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C.H. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Optimization, Approximation, and Complexity Classes. J. Comput. System Sci.\u00a043(3), 425\u2013440 (1991)","journal-title":"J. Comput. System Sci."},{"issue":"1","key":"21_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/moor.18.1.1","volume":"18","author":"C.H. Papadimitriou","year":"1993","unstructured":"Papadimitriou, C.H., Yannakakis, M.: The Traveling Salesman Problem with Distances One and Two. Math. Oper. Res.\u00a018(1), 1\u201311 (1993)","journal-title":"Math. Oper. Res."},{"key":"21_CR17","unstructured":"Robins, G., Zelikovsky, A.: Improved Steiner Tree Approximation in Graphs. In: Proc. of SODA 2000, pp. 770\u2013779 (2000)"},{"key":"21_CR18","unstructured":"Seta, T.: The Complexity of Puzzles, Cross Sum and Their Another Solution Problems (ASP). Senior Thesis, Department of Infomation Science, the Faculty of Science, the University of Tokyo (2002)"},{"key":"21_CR19","unstructured":"Ueda, N., Nagao, T.: NP-Completeness Results for Nonogram via Parsimonious Reductions. Technical report, Tokyo Institute of Technology (1996)"},{"issue":"3","key":"21_CR20","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1137\/0138030","volume":"38","author":"M. Yannakakis","year":"1980","unstructured":"Yannakakis, M., Gavril, F.: Edge Dominating Sets in Graphs. SIAM J. Appl. Math.\u00a038(3), 364\u2013372 (1980)","journal-title":"SIAM J. Appl. Math."},{"key":"21_CR21","unstructured":"Yato, T., Seta, T.: Complexity and Completeness of Finding Another Solution and its Application to Puzzles. In: Proceedings of the National Meeting of the Information Processing Society of Japan (IPSJ) (2002)"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-69733-6_21.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T00:44:48Z","timestamp":1620002688000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-69733-6_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540697329","9783540697336"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-69733-6_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}