{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T16:29:09Z","timestamp":1710347349876},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2010,10,22]],"date-time":"2010-10-22T00:00:00Z","timestamp":1287705600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2012,7]]},"DOI":"10.1007\/s00453-010-9463-4","type":"journal-article","created":{"date-parts":[[2010,10,21]],"date-time":"2010-10-21T10:49:44Z","timestamp":1287658184000},"page":"588-601","source":"Crossref","is-referenced-by-count":7,"title":["The Complexity of Counting Eulerian Tours in\u00a04-regular Graphs"],"prefix":"10.1007","volume":"63","author":[{"given":"Qi","family":"Ge","sequence":"first","affiliation":[]},{"given":"Daniel","family":"\u0160tefankovi\u010d","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,10,22]]},"reference":[{"issue":"3","key":"9463_CR1","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/0166-218X(93)E0172-U","volume":"59","author":"L.D. Andersen","year":"1995","unstructured":"Andersen, L.D., Fleischner, H.: The NP-completeness of finding A-trails in Eulerian graphs and of finding spanning trees in hypergraphs. Discrete Appl. Math. 59(3), 203\u2013214 (1995)","journal-title":"Discrete Appl. Math."},{"key":"9463_CR2","volume-title":"Algorithmic Number Theory. Vol. 1. Foundations of Computing Series","author":"E. Bach","year":"1996","unstructured":"Bach, E., Shallit, J.: Algorithmic Number Theory. Vol. 1. Foundations of Computing Series. MIT Press, Cambridge (1996)"},{"issue":"1","key":"9463_CR3","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/0166-218X(87)90045-X","volume":"18","author":"S.W. Bent","year":"1987","unstructured":"Bent, S.W., Manber, U.: On nonintersecting Eulerian circuits. Discrete Appl. Math. 18(1), 87\u201394 (1987)","journal-title":"Discrete Appl. Math."},{"key":"9463_CR4","first-page":"259","volume-title":"ALENEX\/ANALCO","author":"G. Brightwell","year":"2005","unstructured":"Brightwell, G., Winkler, P.: Counting Eulerian circuits is #P-complete. In: ALENEX\/ANALCO, pp.\u00a0259\u2013262 (2005)"},{"key":"9463_CR5","unstructured":"Creed, P.: Counting and sampling problems on Eulerian graphs. Submitted Ph.D. Dissertation, University of Edinburgh (2010)"},{"key":"9463_CR6","unstructured":"Dvo\u0159\u00e1k, Z.: Eulerian tours in graphs with forbidden transitions and bounded degree. KAM-DIMATIA (669) (2004)"},{"issue":"3","key":"9463_CR7","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1007\/s00453-003-1073-y","volume":"38","author":"M. Dyer","year":"2004","unstructured":"Dyer, M., Goldberg, L.A., Greenhill, C., Jerrum, M.: The relative complexity of approximate counting problems. Algorithmica 38(3), 471\u2013500 (2004)","journal-title":"Algorithmica"},{"key":"9463_CR8","series-title":"Annals of Discrete Mathematics","volume-title":"Eulerian Graphs and Related Topics. Part 1. Vol. 1","author":"H. Fleischner","year":"1990","unstructured":"Fleischner, H.: Eulerian Graphs and Related Topics. Part 1. Vol. 1. Annals of Discrete Mathematics, vol.\u00a045. North-Holland, Amsterdam (1990)"},{"key":"9463_CR9","first-page":"638","volume-title":"LATIN","author":"Q. Ge","year":"2010","unstructured":"Ge, Q., \u0160tefankovi\u010d, D.: The complexity of counting Eulerian tours in 4-regular graphs. In: LATIN, pp. 638\u2013649 (2010)"},{"key":"9463_CR10","doi-asserted-by":"crossref","unstructured":"Ge, Q., \u0160tefankovi\u010d, D.: The complexity of counting Eulerian tours in 4-regular graphs. arXiv:1009.5019 (2010)","DOI":"10.1007\/978-3-642-12200-2_55"},{"key":"9463_CR11","unstructured":"Jerrum, M.: Review MR1822924 (2002k:68197) of [14]. MathSciNet (2002)"},{"key":"9463_CR12","series-title":"Lectures in Mathematics ETH Z\u00fcrich","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-0348-8005-3","volume-title":"Counting, Sampling and Integrating: Algorithms and Complexity","author":"M. Jerrum","year":"2003","unstructured":"Jerrum, M.: Counting, Sampling and Integrating: Algorithms and Complexity. Lectures in Mathematics ETH Z\u00fcrich. Birkh\u00e4user, Basel (2003)"},{"key":"9463_CR13","first-page":"219","volume-title":"Theory of Graphs","author":"A. Kotzig","year":"1968","unstructured":"Kotzig, A.: Eulerian lines in finite 4-valent graphs and their transformations. In: Theory of Graphs, Proc. Colloq., Tihany, 1966, pp. 219\u2013230. Academic Press, San Diego (1968)"},{"issue":"3","key":"9463_CR14","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1007\/s00453-001-0018-6","volume":"30","author":"P. Tetali","year":"2001","unstructured":"Tetali, P., Vempala, S.: Random sampling of Euler tours. Algorithmica 30(3), 376\u2013385 (2001)","journal-title":"Algorithmica"},{"key":"9463_CR15","volume-title":"Approximation Algorithms","author":"V.V. Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, Berlin (2001)"},{"issue":"1","key":"9463_CR16","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1214\/aoap\/1075828054","volume":"14","author":"D.B. Wilson","year":"2004","unstructured":"Wilson, D.B.: Mixing times of Lozenge tiling and card shuffling Markov chains. Ann. Appl. Probab. 14(1), 274\u2013325 (2004)","journal-title":"Ann. Appl. Probab."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9463-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-010-9463-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9463-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,5]],"date-time":"2019-06-05T14:39:26Z","timestamp":1559745566000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-010-9463-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,10,22]]},"references-count":16,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,7]]}},"alternative-id":["9463"],"URL":"https:\/\/doi.org\/10.1007\/s00453-010-9463-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,10,22]]}}}