{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:43Z","timestamp":1740109303201,"version":"3.37.3"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2019,1,30]],"date-time":"2019-01-30T00:00:00Z","timestamp":1548806400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["P26696"],"award-info":[{"award-number":["P26696"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["677651"],"award-info":[{"award-number":["677651"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,6]]},"DOI":"10.1007\/s00453-019-00546-z","type":"journal-article","created":{"date-parts":[[2019,1,31]],"date-time":"2019-01-31T01:05:16Z","timestamp":1548896716000},"page":"2606-2632","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the Complexity Landscape of Connected f-Factor Problems"],"prefix":"10.1007","volume":"81","author":[{"given":"R.","family":"Ganian","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"N. S.","family":"Narayanaswamy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S.","family":"Ordyniak","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6199-7583","authenticated-orcid":false,"given":"C. S.","family":"Rahul","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M. S.","family":"Ramanujan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,1,30]]},"reference":[{"issue":"1","key":"546_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/jgt.3190090103","volume":"9","author":"J Akiyama","year":"1985","unstructured":"Akiyama, J., Kano, M.: Factors and factorizations of graphsa survey. J. Graph Theory 9(1), 1\u201342 (1985)","journal-title":"J. Graph Theory"},{"key":"546_CR2","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1145\/321105.321111","volume":"9","author":"RE Bellman","year":"1962","unstructured":"Bellman, R.E.: Dynamic programming treatment of the traveling salesman problem. J. ACM 9, 61\u201363 (1962)","journal-title":"J. ACM"},{"issue":"1\u20132","key":"546_CR3","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/0166-218X(90)90129-Z","volume":"27","author":"F Cheah","year":"1990","unstructured":"Cheah, F., Corneil, D.G.: The complexity of regular subgraph recognition. Discrete Appl. Math. 27(1\u20132), 59\u201368 (1990)","journal-title":"Discrete Appl. Math."},{"key":"546_CR4","first-page":"103","volume":"52","author":"FRK Chung","year":"1981","unstructured":"Chung, F.R.K., Graham, R.L.: Recent results in graph decompositions. Lond. Math. Soc. Lect. Note Ser. 52, 103\u2013123 (1981)","journal-title":"Lond. Math. Soc. Lect. Note Ser."},{"issue":"2","key":"546_CR5","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1007\/s00224-016-9723-z","volume":"62","author":"K Cornelissen","year":"2018","unstructured":"Cornelissen, K., Hoeksma, R., Manthey, B., Narayanaswamy, N.S., Rahul, C.S., Waanders, M.: Approximation algorithms for connected graph factors of minimum weight. Theory Comput. Syst. 62(2), 441\u2013464 (2018)","journal-title":"Theory Comput. Syst."},{"key":"546_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1007\/978-3-319-08001-7_11","volume-title":"Approximation and Online Algorithms","author":"K Cornelissen","year":"2014","unstructured":"Cornelissen, K., Hoeksma, R., Manthey, B., Narayanaswamy, N.S., Rahul, C.S.: Approximability of connected factors. In: Kaklamanis, C., Pruhs, K. (eds.) Approximation and Online Algorithms. Lecture Notes in Computer Science, vol. 8447, pp. 120\u2013131. Springer, Berlin (2014)"},{"key":"546_CR7","unstructured":"Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., van Rooij, J.M.M., Onufry Wojtaszczyk, J.: Solving connectivity problems parameterized by treewidth in single exponential time. In: Ostrovsky, R. (ed.) IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22\u201325, 2011, pp. 150\u2013159. IEEE Computer Society (2011)"},{"key":"546_CR8","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York (1979)"},{"issue":"1","key":"546_CR9","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/j.jcss.2016.06.001","volume":"83","author":"GZ Gutin","year":"2017","unstructured":"Gutin, G.Z., Wahlstr\u00f6m, M., Yeo, A.: Rural postman parameterized by the number of components of required edges. J. Comput. Syst. Sci. 83(1), 121\u2013131 (2017)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"546_CR10","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1137\/0110015","volume":"10","author":"M Held","year":"1962","unstructured":"Held, M., Karp, R.: A dynamic programming approach to sequencing problems. J. Soc. Ind. Appl. Math. 10(1), 196\u2013210 (1962)","journal-title":"J. Soc. Ind. Appl. Math."},{"issue":"4","key":"546_CR11","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"10","key":"546_CR12","doi-asserted-by":"publisher","first-page":"1689","DOI":"10.1016\/j.disc.2012.01.020","volume":"312","author":"T Kaiser","year":"2012","unstructured":"Kaiser, T.: A short proof of the tree-packing theorem. Discrete Math. 312(10), 1689\u20131691 (2012)","journal-title":"Discrete Math."},{"issue":"1","key":"546_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00373-004-0587-7","volume":"21","author":"M Kouider","year":"2005","unstructured":"Kouider, M., Vestergaard, P.D.: Connected factors in graphs\u2014a survey. Graphs Comb. 21(1), 1\u201326 (2005)","journal-title":"Graphs Comb."},{"key":"546_CR14","volume-title":"Matching Theory, Volume 121 of North-Holland Mathematics Studies","author":"L Lov\u00e1sz","year":"1986","unstructured":"Lov\u00e1sz, L., Plummer, M.D.: Matching Theory, Volume 121 of North-Holland Mathematics Studies. Elsevier, Amsterdam (1986)"},{"key":"546_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1007\/978-3-319-20297-6_23","volume-title":"Computer Science-Theory and Applications\u201310th International Computer Science Symposium in Russia, CSR 2015, Listvyanka, Russia, July 13\u201317, 2015, Proceedings","author":"NS Narayanaswamy","year":"2015","unstructured":"Narayanaswamy, N.S., Rahul, C.S.: Approximation and exact algorithms for special cases of connected f-factors. In: Beklemishev, L.D., Musatov, D.V. (eds.) Computer Science-Theory and Applications\u201310th International Computer Science Symposium in Russia, CSR 2015, Listvyanka, Russia, July 13\u201317, 2015, Proceedings. Lecture Notes in Computer Science, vol. 9139, pp. 350\u2013363. Springer, Berlin (2015)"},{"issue":"1","key":"546_CR16","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/BF02392606","volume":"15","author":"J Petersen","year":"1891","unstructured":"Petersen, J.: Die Theorie der regul\u00e4ren graphs. Acta Math. 15(1), 193\u2013220 (1891)","journal-title":"Acta Math."},{"key":"546_CR17","unstructured":"Philip, G., Ramanujan, M.S.: Vertex exponential algorithms for connected f-factors. In: Venkatesh, R., and Suresh, S.P. (eds.) 34th International Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS 2014, December 15\u201317, 2014, New Delhi, India, Volume\u00a029 of LIPIcs, pp. 61\u201371. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2014)"},{"issue":"7\u20138","key":"546_CR18","doi-asserted-by":"publisher","first-page":"791","DOI":"10.1016\/j.disc.2005.11.059","volume":"307","author":"MD Plummer","year":"2007","unstructured":"Plummer, M.D.: Graph factors and factorization: 1985\u20132003: a survey. Discrete Math. 307(7\u20138), 791\u2013821 (2007)","journal-title":"Discrete Math."},{"issue":"4","key":"546_CR19","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"JT Schwartz","year":"1980","unstructured":"Schwartz, J.T.: Fast probabilistic algorithms for verification of polynomial identities. J. ACM 27(4), 701\u2013717 (1980)","journal-title":"J. ACM"},{"issue":"2","key":"546_CR20","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1112\/jlms\/s1-22.2.107","volume":"1","author":"WT Tutte","year":"1947","unstructured":"Tutte, W.T.: The factorization of linear graphs. J. Lond. Math. Soc. 1(2), 107\u2013111 (1947)","journal-title":"J. Lond. Math. Soc."},{"issue":"3","key":"546_CR21","doi-asserted-by":"publisher","first-page":"314","DOI":"10.4153\/CJM-1952-028-2","volume":"4","author":"WT Tutte","year":"1952","unstructured":"Tutte, W.T.: The factors of graphs. Can. J. Math. 4(3), 314\u2013328 (1952)","journal-title":"Can. J. Math."},{"issue":"1954","key":"546_CR22","doi-asserted-by":"publisher","first-page":"347","DOI":"10.4153\/CJM-1954-033-3","volume":"6","author":"WT Tutte","year":"1954","unstructured":"Tutte, W.T.: A short proof of the factor theorem for finite graphs. Can. J. Math. 6(1954), 347\u2013352 (1954)","journal-title":"Can. J. Math."},{"key":"546_CR23","unstructured":"Wahlstr\u00f6m, M.: Abusing the Tutte matrix: an algebraic instance compression for the k-set-cycle problem. In: Natacha, P., Thomas, W. (eds.) 30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013, February 27\u2013March 2, 2013, Kiel, Germany, Volume 20 of LIPIcs, pp. 341\u2013352. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2013)"},{"key":"546_CR24","volume-title":"Introduction to Graph Theory","author":"DB West","year":"2001","unstructured":"West, D.B.: Introduction to Graph Theory. Prentice Hall, Upper Saddle River (2001)"},{"key":"546_CR25","doi-asserted-by":"crossref","unstructured":"Zippel, R.: Probabilistic algorithms for sparse polynomials. In: Ng, E.W. (ed.) Symbolic and Algebraic Computation, EUROSAM \u201979, An International Symposium on Symbolic and Algebraic Computation, Marseille, France, June 1979, Proceedings, Volume 72 of Lecture Notes in Computer Science, pp. 216\u2013226. Springer, Berlin (1979)","DOI":"10.1007\/3-540-09519-5_73"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00546-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00546-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00546-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,29]],"date-time":"2020-01-29T19:05:08Z","timestamp":1580324708000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00546-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1,30]]},"references-count":25,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2019,6]]}},"alternative-id":["546"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00546-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2019,1,30]]},"assertion":[{"value":"12 October 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 January 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 January 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}