Consider connected undirected simple graph G = (V, E). Let n = |V | and m = |E| be respectively the number of nodes and edges. A cycle C is a subgraph in which every node has even degree (number of incident edges). It can be represented by an edge incidence vector χ(C) in {0, 1}^m, where the component χ(C)[e] corresponding to the edge e ∈ E is 1 if e ∈ C, and 0 otherwise. The composition of two cycles C1 and C2 is a cycle C3 where χ(C3) is equal to the sum modulo 2 of χ(C1) and χ(C2). All the cycles of G form a vector space over GF(2), called the cycle space of G. A cycle basis C is a maximal set of independent cycles. Every cycle can thus be obtained by the composition of some cycles of C. For a connected graph, the dimension of C is equal to ν := m − n + 1.Cycle bases have been attracting growing attention in combinatorial optimization.In particular, assigned a nonnegative weight to each edge, the problem of ﬁndinga cycle basis of minimum total weight in undirected graphs and several variantsarising from applications have been extensively studied (e.g. [1]). See survey [3]and the references therein.In this work, we investigate a natural related problem, that we refer to as the Cycle basis with limited edge overlap (CBEO). Given an undirected graph G with a nonnegative integer bound b[e] on each edge e ∈ E, ﬁnd a cycle basis C such that each edge e ∈ E belongs to at most b[e] cycles of C. In the uniform case all the edge bounds are equal.Such a cycle basis is relevant for example in the analysis of electrical networks.When one wishes to check that Kirchhoff’s law is satisﬁed along all the loops, it ispossible to focus only on those corresponding to the cycles of a basis. In orderto reduce the probability of damaging the links, it may be desirable to limit thenumber of times each link is tested.

### On cycle bases with limited edge overlap.

#### Abstract

Consider connected undirected simple graph G = (V, E). Let n = |V | and m = |E| be respectively the number of nodes and edges. A cycle C is a subgraph in which every node has even degree (number of incident edges). It can be represented by an edge incidence vector χ(C) in {0, 1}^m, where the component χ(C)[e] corresponding to the edge e ∈ E is 1 if e ∈ C, and 0 otherwise. The composition of two cycles C1 and C2 is a cycle C3 where χ(C3) is equal to the sum modulo 2 of χ(C1) and χ(C2). All the cycles of G form a vector space over GF(2), called the cycle space of G. A cycle basis C is a maximal set of independent cycles. Every cycle can thus be obtained by the composition of some cycles of C. For a connected graph, the dimension of C is equal to ν := m − n + 1.Cycle bases have been attracting growing attention in combinatorial optimization.In particular, assigned a nonnegative weight to each edge, the problem of ﬁndinga cycle basis of minimum total weight in undirected graphs and several variantsarising from applications have been extensively studied (e.g. [1]). See survey [3]and the references therein.In this work, we investigate a natural related problem, that we refer to as the Cycle basis with limited edge overlap (CBEO). Given an undirected graph G with a nonnegative integer bound b[e] on each edge e ∈ E, ﬁnd a cycle basis C such that each edge e ∈ E belongs to at most b[e] cycles of C. In the uniform case all the edge bounds are equal.Such a cycle basis is relevant for example in the analysis of electrical networks.When one wishes to check that Kirchhoff’s law is satisﬁed along all the loops, it ispossible to focus only on those corresponding to the cycles of a basis. In orderto reduce the probability of damaging the links, it may be desirable to limit thenumber of times each link is tested.
##### Scheda breve Scheda completa Scheda completa (DC)
2011
undirected graphs; cycle basis; edge overlap
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11562/392252
• ND
• 0
• ND