{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T11:39:18Z","timestamp":1725795558656},"publisher-location":"Cham","reference-count":16,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319080000"},{"type":"electronic","value":"9783319080017"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-08001-7_14","type":"book-chapter","created":{"date-parts":[[2014,6,10]],"date-time":"2014-06-10T16:53:00Z","timestamp":1402419180000},"page":"156-167","source":"Crossref","is-referenced-by-count":2,"title":["Counting Approximately-Shortest Paths in Directed Acyclic Graphs"],"prefix":"10.1007","author":[{"given":"Mat\u00fa\u0161","family":"Mihal\u00e1k","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rastislav","family":"\u0160r\u00e1mek","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Widmayer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"14_CR1","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1006\/jagm.1996.0851","volume":"24","author":"A.Z. Broder","year":"1997","unstructured":"Broder, A.Z., Mayr, E.W.: Counting minimum weight spanning trees. J. Algorithms\u00a024, 171\u2013176 (1997)","journal-title":"J. Algorithms"},{"key":"14_CR2","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1145\/2422436.2422491","volume-title":"Proc. 4th Conference on Innovations in Theoretical Computer Sciencei (ITCS)","author":"J.M. Buhmann","year":"2013","unstructured":"Buhmann, J.M., Mihal\u00e1k, M., \u0160r\u00e1mek, R., Widmayer, P.: Robust optimization in the presence of uncertainty. In: Proc. 4th Conference on Innovations in Theoretical Computer Sciencei (ITCS), pp. 505\u2013514. ACM, New York (2013)"},{"issue":"1","key":"14_CR3","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1006\/jmbi.1997.0951","volume":"268","author":"C. Burge","year":"1997","unstructured":"Burge, C., Karlin, S.: Prediction of complete gene structures in human genomic DNA. Journal of Molecular Biology\u00a0268(1), 78\u201394 (1997)","journal-title":"Journal of Molecular Biology"},{"issue":"3","key":"14_CR4","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1089\/10665270152530872","volume":"8","author":"T. Chen","year":"2001","unstructured":"Chen, T., Kao, M.Y., Tepel, M., Rush, J., Church, G.M.: A dynamic programming approach to de novo peptide sequencing via tandem mass spectrometry. Journal of Computational Biology\u00a08(3), 325\u2013337 (2001)","journal-title":"Journal of Computational Biology"},{"key":"14_CR5","doi-asserted-by":"crossref","unstructured":"Durbin, R., Eddy, S.R., Krogh, A., Mitchison, G.: Biological sequence analysis: Probabilistic models of proteins and nucleic acids. Cambridge university press (1998)","DOI":"10.1017\/CBO9780511790492"},{"issue":"3","key":"14_CR6","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1017\/S0963548300000675","volume":"2","author":"M. Dyer","year":"1993","unstructured":"Dyer, M., Frieze, A., Kannan, R., Kapoor, A., Perkovic, L., Vazirani, U.: A mildly exponential time algorithm for approximating the number of solutions to a multidimensional knapsack problem. Combinatorics, Probability and Computing\u00a02(3), 271\u2013284 (1993)","journal-title":"Combinatorics, Probability and Computing"},{"key":"14_CR7","doi-asserted-by":"crossref","unstructured":"Gopalan, P., Klivans, A., Meka, R., \u0160tefankovi\u010d, D., Vempala, S., Vigoda, E.: An FPTAS for # knapsack and related counting problems. In: Proc. 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 817\u2013826 (2011)","DOI":"10.1109\/FOCS.2011.32"},{"issue":"1-2","key":"14_CR8","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/BF01010403","volume":"48","author":"M. Jerrum","year":"1987","unstructured":"Jerrum, M.: Two-dimensional monomer-dimer systems are computationally intractable. Journal of Statistical Physics\u00a048(1-2), 121\u2013134 (1987)","journal-title":"Journal of Statistical Physics"},{"key":"14_CR9","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. Springer (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"14_CR10","doi-asserted-by":"crossref","unstructured":"Kreher, D.L., Stinson, D.R.: Combinatorial Algorithms: Generation, Enumeration, and Search (1998)","DOI":"10.1145\/309739.309744"},{"issue":"1","key":"14_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1089\/106652703763255633","volume":"10","author":"B. Lu","year":"2003","unstructured":"Lu, B., Chen, T.: A suboptimal algorithm for de novo peptide sequencing via tandem mass spectrometry. Journal of Computational Biology\u00a010(1), 1\u201312 (2003)","journal-title":"Journal of Computational Biology"},{"key":"14_CR12","doi-asserted-by":"crossref","unstructured":"Mihal\u00e1k, M., \u0160r\u00e1mek, R., Widmayer, P.: Counting approximately-shortest paths in directed acyclic graphs. arXiv preprint arXiv:1304.6707 (2013)","DOI":"10.1007\/978-3-319-08001-7_14"},{"key":"14_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/BFb0029805","volume-title":"Combinatorial Pattern Matching","author":"D. Naor","year":"1993","unstructured":"Naor, D., Brutlag, D.: On suboptimal alignments of biological sequences. In: Apostolico, A., Crochemore, M., Galil, Z., Manber, U. (eds.) CPM 1993. LNCS, vol.\u00a0684, pp. 179\u2013196. Springer, Heidelberg (1993)"},{"issue":"2","key":"14_CR14","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1137\/11083976X","volume":"41","author":"D. \u0160tefankovi\u010d","year":"2012","unstructured":"\u0160tefankovi\u010d, D., Vempala, S., Vigoda, E.: A deterministic polynomial-time approximation scheme for counting knapsack solutions. SIAM Journal on Computing\u00a041(2), 356\u2013366 (2012)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"14_CR15","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of computing the permanent. Theoretical Computer Science\u00a08(2), 189\u2013201 (1979)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"14_CR16","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM J. Comput.\u00a08(3), 410\u2013421 (1979)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-08001-7_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,7]],"date-time":"2022-04-07T12:57:17Z","timestamp":1649336237000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-08001-7_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319080000","9783319080017"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-08001-7_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}