Thumbnail Image

New Length Bounds for Cycle Bases

Elkin, Michael; Liebchen, Christian; Rizzi, Romeo

Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin

Based on a recent work by Abraham, Bartal and Neiman (2007), we construct a strictly fundamental cycle basis of length O(n2) for any unweighted graph, whence proving the conjecture of Deo et al. (1982).