{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:54:03Z","timestamp":1773482043349,"version":"3.50.1"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,9,18]],"date-time":"2014-09-18T00:00:00Z","timestamp":1410998400000},"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":["Theory Comput Syst"],"published-print":{"date-parts":[[2016,1]]},"DOI":"10.1007\/s00224-014-9571-7","type":"journal-article","created":{"date-parts":[[2014,9,17]],"date-time":"2014-09-17T17:32:14Z","timestamp":1410975134000},"page":"45-59","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Approximately Counting Approximately-Shortest Paths in Directed Acyclic Graphs"],"prefix":"10.1007","volume":"58","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","published-online":{"date-parts":[[2014,9,18]]},"reference":[{"key":"9571_CR1","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1006\/jagm.1996.0851","volume":"24","author":"AZ Broder","year":"1997","unstructured":"Broder, A.Z., Mayr, E.W.: Counting minimum weight spanning trees. J. Algorithm. 24, 171\u2013176 (1997)","journal-title":"J. Algorithm."},{"key":"9571_CR2","doi-asserted-by":"crossref","unstructured":"Buhmann, J.M., Mihal\u00e1k, M., \u0160r\u00e1mek, R., Widmayer, P.: Robust optimization in the presence of uncertainty. In: Proceedings of the 4th Conference on Innovations in Theoretical Computer Sciencei (ITCS). pp. 505\u2013514. ACM, New York (2013)","DOI":"10.1145\/2422436.2422491"},{"issue":"1","key":"9571_CR3","doi-asserted-by":"crossref","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. J. Mol. Biol. 268(1), 78\u201394 (1997)","journal-title":"J. Mol. Biol."},{"issue":"3","key":"9571_CR4","doi-asserted-by":"crossref","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. J. Comput. Biol. 8(3), 325\u2013337 (2001)","journal-title":"J. Comput. Biol."},{"key":"9571_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":"9571_CR6","doi-asserted-by":"crossref","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. Comb. Probab. Comput. 2(3), 271\u2013284 (1993)","journal-title":"Comb. Probab. Comput."},{"key":"9571_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: Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS). pp. 817\u2013826 (2011)","DOI":"10.1109\/FOCS.2011.32"},{"issue":"1\u20132","key":"9571_CR8","doi-asserted-by":"crossref","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. J. Stat. Phys. 48(1\u20132), 121\u2013134 (1987)","journal-title":"J. Stat. Phys."},{"key":"9571_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":"9571_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":"9571_CR11","doi-asserted-by":"crossref","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. J. Comput. Biol. 10(1), 1\u201312 (2003)","journal-title":"J. Comput. Biol."},{"key":"9571_CR12","doi-asserted-by":"crossref","unstructured":"Naor, D., Brutlag, D.: On suboptimal alignments of biological sequences. In: Proceedings of the 4th Annual Symposium on Combinatorial Pattern Matching (CPM). pp. 179\u2013196. Springer (1993)","DOI":"10.1007\/BFb0029805"},{"key":"9571_CR13","unstructured":"Rizzi, R., Tomescu, A.I.: Combinatorial decomposition approaches for efficient counting and random generation fptases. CoRR abs\/1307.2347v2 (2013)"},{"issue":"2","key":"9571_CR14","doi-asserted-by":"crossref","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 J. Comput. 41(2), 356\u2013366 (2012)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9571_CR15","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"LG Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of computing the permanent. Theor. Comput. Sci. 8(2), 189\u2013201 (1979)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"9571_CR16","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"LG Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM J. Comput. 8(3), 410\u2013421 (1979)","journal-title":"SIAM J. Comput."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-014-9571-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-014-9571-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-014-9571-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,17]],"date-time":"2022-04-17T08:22:41Z","timestamp":1650183761000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-014-9571-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,9,18]]},"references-count":16,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["9571"],"URL":"https:\/\/doi.org\/10.1007\/s00224-014-9571-7","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,9,18]]}}}