{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T10:12:27Z","timestamp":1784110347737,"version":"3.55.0"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2007,10,27]],"date-time":"2007-10-27T00:00:00Z","timestamp":1193443200000},"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":[[2009,3]]},"DOI":"10.1007\/s00453-007-9112-8","type":"journal-article","created":{"date-parts":[[2007,10,26]],"date-time":"2007-10-26T17:25:11Z","timestamp":1193419511000},"page":"402-424","source":"Crossref","is-referenced-by-count":15,"title":["Minimum Weakly Fundamental Cycle Bases Are Hard To Find"],"prefix":"10.1007","volume":"53","author":[{"given":"Romeo","family":"Rizzi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2007,10,27]]},"reference":[{"issue":"1\u20132","key":"9112_CR1","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/S0304-3975(98)00158-3","volume":"237","author":"P. Alimonti","year":"2000","unstructured":"Alimonti, P., Kann, V.: Some APX-completeness results for cubic graphs. Theor. Comput. Sci. 237(1\u20132), 123\u2013134 (2000)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"9112_CR2","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1137\/S0097539792224474","volume":"24","author":"N. Alon","year":"1995","unstructured":"Alon, N., Karp, R.M., Peleg, D., West, D.B.: A graph-theoretic game and its application to the k-server problem. SIAM J. Comput. 24(1), 78\u2013100 (1995)","journal-title":"SIAM J. Comput."},{"key":"9112_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1007\/978-3-540-24838-5_2","volume-title":"WEA","author":"E. Amaldi","year":"2004","unstructured":"Amaldi, E., Liberti, L., Maculan, N., Maffioli, F.: Efficient edge-swapping heuristics for finding minimum fundamental cycle bases. In: Ribeiro, C.C., Martins, S.L. (eds.) WEA. Lecture Notes in Computer Science, vol.\u00a03059, pp.\u00a014\u201329. Springer, Berlin (2004)"},{"key":"9112_CR4","volume-title":"Combinatorial Optimization Problems and their Approximability Properties","author":"G. Ausiello","year":"1999","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Combinatorial Optimization Problems and their Approximability Properties. Springer, Berlin (1999)"},{"key":"9112_CR5","doi-asserted-by":"crossref","unstructured":"Bartal, Y.: On approximating arbitrary metrics by tree metrics. In: Proceedings of the 37th Annual Symposium on Foundations of Computer Science, STOCS, pp.\u00a0161\u2013168 (1998)","DOI":"10.1145\/276698.276725"},{"issue":"1","key":"9112_CR6","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/s00453-004-1098-x","volume":"40","author":"F. Berger","year":"2004","unstructured":"Berger, F., Gritzmann, P., de Vries, S.: Minimum cycle bases for network graphs. Algorithmica 40(1), 51\u201362 (2004)","journal-title":"Algorithmica"},{"key":"9112_CR7","volume-title":"Extremal Graph Theory","author":"B. Bollob\u00e1s","year":"1978","unstructured":"Bollob\u00e1s, B.: Extremal Graph Theory. Academic Press, New York (1978)"},{"key":"9112_CR8","series-title":"Graduate Texts in Mathematics","volume-title":"Modern Graph Theory","author":"B. Bollob\u00e1s","year":"2002","unstructured":"Bollob\u00e1s, B.: Modern Graph Theory, 2nd edn. Graduate Texts in Mathematics, vol.\u00a0184. Springer, Berlin (2002)","edition":"2"},{"issue":"1","key":"9112_CR9","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/S0196-6774(03)00052-X","volume":"48","author":"A. Caprara","year":"2003","unstructured":"Caprara, A., Panconesi, A., Rizzi, R.: Packing cycles in undirected graphs. J.\u00a0Algorithms 48(1), 239\u2013256 (2003)","journal-title":"J.\u00a0Algorithms"},{"key":"9112_CR10","unstructured":"de Pina, J.C.: Applications of shortest path methods. PhD thesis University of Amsterdam (1995)"},{"issue":"1","key":"9112_CR11","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1145\/355984.355988","volume":"8","author":"M.P.N. Deo","year":"1982","unstructured":"Deo, M.P.N., Prabhu, G.M., Krishnomoorthy, M.S.: Algorithms for generating fundamental cycles in a graph. ACM Trans. Math. Softw. 8(1), 26\u201342 (1982)","journal-title":"ACM Trans. Math. Softw."},{"key":"9112_CR12","doi-asserted-by":"crossref","unstructured":"Elkin, M., Liebchen, C., Rizzi, R.: New length bounds for cycle bases. Inf. Process. Lett. (2007, to appear)","DOI":"10.1016\/j.ipl.2007.06.013"},{"key":"9112_CR13","doi-asserted-by":"crossref","first-page":"3","DOI":"10.5486\/PMD.1962.9.1-2.02","volume":"9","author":"P. Erd\u00f6s","year":"1962","unstructured":"Erd\u00f6s, P., P\u00f3sa, L.: On the maximal number of disjoint circuits of a graph. Publ. Math. Debr. 9, 3\u201312 (1962)","journal-title":"Publ. Math. Debr."},{"key":"9112_CR14","series-title":"Lecture Notes in Computer Science","first-page":"151","volume-title":"WAOA","author":"G. Galbiati","year":"2003","unstructured":"Galbiati, G., Amaldi, E.: On the approximability of the minimum fundamental cycle basis problem. In: Jansen, K., Solis-Oba, R. (eds.) WAOA. Lecture Notes in Computer Science, vol.\u00a02909, pp.\u00a0151\u2013164. Springer, Berlin (2003)"},{"key":"9112_CR15","unstructured":"Gleiss, P.M.: Short cycles. PhD thesis, Universit\u00e4t Wien (2001). http:\/\/www.tbi.univie.ac.at\/papers\/Abstracts\/pmg_diss.pdf"},{"key":"9112_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1007\/3-540-45471-3_21","volume-title":"SWAT","author":"A. Golynski","year":"2002","unstructured":"Golynski, A., Horton, J.D.: A polynomial time algorithm to find the minimum cycle basis of a regular matroid. In: Penttonen, M., Schmidt, E.M. (eds.) SWAT. Lecture Notes in Computer Science, vol.\u00a02368, pp.\u00a0200\u2013209. Springer, Berlin (2002)"},{"key":"9112_CR17","unstructured":"Hariharan, R., Kavitha, T., Mehlhorn, K.: A faster deterministic algorithm for minimum cycle bases in directed graphs. Kurt Mehlhorn\u2019s List of Publications 191, Max-Planck-Institute Saarbr\u00fccken (2005). http:\/\/www.mpi-sb.mpg.de\/~mehlhorn\/ftp\/ImprovedDirCycleBasis.ps"},{"key":"9112_CR18","doi-asserted-by":"crossref","first-page":"713","DOI":"10.1137\/0210054","volume":"10","author":"I. Holyer","year":"1981","unstructured":"Holyer, I.: The ${\\mathcal{NP}}$ -completeness of some edge-partition problems. SIAM J. Comput. 10, 713\u2013717 (1981)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9112_CR19","doi-asserted-by":"crossref","first-page":"358","DOI":"10.1137\/0216026","volume":"16","author":"J.D. Horton","year":"1987","unstructured":"Horton, J.D.: A\u00a0polynomial-time algorithm to find the shortest cycle basis of a graph. SIAM J. Comput. 16(2), 358\u2013366 (1987)","journal-title":"SIAM J. Comput."},{"key":"9112_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"846","DOI":"10.1007\/978-3-540-27836-8_71","volume-title":"ICALP","author":"T. Kavitha","year":"2004","unstructured":"Kavitha, T., Mehlhorn, K., Michail, D., Paluch, K.E.: A\u00a0faster algorithm for minimum cycle basis of graphs. In: Diaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sanella, D. (eds.) ICALP. Lecture Notes in Computer Science, vol.\u00a03142, pp.\u00a0846\u2013857. Springer, Berlin (2004)"},{"key":"9112_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"654","DOI":"10.1007\/978-3-540-31856-9_54","volume-title":"STACS","author":"T. Kavitha","year":"2005","unstructured":"Kavitha, T., Mehlhorn, K.: A\u00a0polynomial time algorithm for minimum cycle basis in directed graphs. In: Diekert, V., Durand, B. (eds.) STACS. Lecture Notes in Computer Science, vol.\u00a03404, pp.\u00a0654\u2013665. Springer, Berlin (2005)"},{"key":"9112_CR22","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1002\/andp.18471481202","volume":"72","author":"G.R. Kirchhoff","year":"1847","unstructured":"Kirchhoff, G.R.: \u00dcber die Aufl\u00f6sung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Str\u00f6me gef\u00fchrt wird. Ann. Phys. Chem. 72, 497\u2013508 (1847)","journal-title":"Ann. Phys. Chem."},{"key":"9112_CR23","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/(SICI)1097-0118(199805)28:1<1::AID-JGT1>3.0.CO;2-Q","volume":"28","author":"M. Kochol","year":"1998","unstructured":"Kochol, M.: Hypothetical complexity of the nowhere-zero 5-flow problem. J.\u00a0Graph Theory 28, 1\u201311 (1998)","journal-title":"J.\u00a0Graph Theory"},{"key":"9112_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"715","DOI":"10.1007\/978-3-540-39658-1_64","volume-title":"ESA","author":"C. Liebchen","year":"2003","unstructured":"Liebchen, C.: Finding short integral cycle bases for cyclic timetabling. In: Battista, G.D., Zwick, U. (eds.) ESA. Lecture Notes in Computer Science, vol.\u00a02832, pp.\u00a0715\u2013726. Springer, Berlin (2003)"},{"key":"9112_CR25","unstructured":"Liebchen, C., Peeters, L.W.: On cyclic timetabling and cycles in graphs. Technical Report 761-2002, TU Berlin, Mathematical Institute (2002). ftp:\/\/ftp.math.tu-berlin.de\/pub\/Preprints\/combi\/Report-761-2002.pdf"},{"issue":"3","key":"9112_CR26","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/j.ipl.2005.01.006","volume":"94","author":"C. Liebchen","year":"2005","unstructured":"Liebchen, C., Rizzi, R.: A\u00a0greedy approach to compute a minimum cycle basis of a directed graph. Inf. Process. Lett. 94(3), 107\u2013112 (2005)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"9112_CR27","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/j.dam.2006.06.007","volume":"155","author":"C. Liebchen","year":"2007","unstructured":"Liebchen, C., Rizzi, R.: Classes of cycle bases. Discrete Math. 155(3), 337\u2013355 (2007)","journal-title":"Discrete Math."},{"key":"9112_CR28","volume-title":"Computational Complexity. EATCS Monographs on Theoretical Computer Science","author":"C.H. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: Computational Complexity. EATCS Monographs on Theoretical Computer Science. Addison-Wesley, Reading (1994)"},{"key":"9112_CR29","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1112\/plms\/s1-32.1.277","volume":"32","author":"H. Poincar\u00e9","year":"1900","unstructured":"Poincar\u00e9, H.: Second compl\u00e9ment \u00e0 l\u2019analysis situs. Proc. Lond. Math. Soc. 32, 277\u2013308 (1900)","journal-title":"Proc. Lond. Math. Soc."},{"key":"9112_CR30","unstructured":"Trevisan, L.: Inapproximability of combinatorial optimization problems. In: ECCC, p.\u00a0065 (2004)"},{"key":"9112_CR31","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1016\/0012-365X(88)90226-9","volume":"72","author":"S. Ueno","year":"1988","unstructured":"Ueno, S., Kajitani, Y., Gotoh, S.: On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three. Discrete Math. 72, 355\u2013360 (1988)","journal-title":"Discrete Math."},{"key":"9112_CR32","unstructured":"Veblen, O.: Analysis situs. Amer. Math. Soc. Colloq. Lect. 1916, New York (1922)"},{"key":"9112_CR33","doi-asserted-by":"crossref","first-page":"509","DOI":"10.2307\/2371182","volume":"57","author":"H. Whitney","year":"1935","unstructured":"Whitney, H.: On the abstract properties of linear dependence. Am. J. Math. 57, 509\u2013533 (1935)","journal-title":"Am. J. Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9112-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-007-9112-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9112-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,14]],"date-time":"2023-05-14T14:46:39Z","timestamp":1684075599000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-007-9112-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,10,27]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2009,3]]}},"alternative-id":["9112"],"URL":"https:\/\/doi.org\/10.1007\/s00453-007-9112-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,10,27]]}}}