Abstract | ||
---|---|---|
Let G be a bridgeless graph with m edges and n vertices. It is proved that the edges of G can be covered by circuits whose total length is at most m + (r/r - 1)(n - 1), where r is the minimum length of an even circuit (of G) of length at least 6 (r = infinity, if there is no such circuit). The proof suggests a polynomial-time algorithm for constructing such a cover. |
Year | DOI | Venue |
---|---|---|
1992 | 10.1137/0405039 | SIAM J. Discrete Math. |
Keywords | Field | DocType |
covering | Discrete mathematics,Graph algorithms,Graph,Combinatorics,Vertex (geometry),Eulerian path,Time complexity,Electronic circuit,Mathematics | Journal |
Volume | Issue | ISSN |
5 | 4 | 0895-4801 |
Citations | PageRank | References |
16 | 3.89 | 7 |
Authors | ||
1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Genghua Fan | 1 | 412 | 65.22 |