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 findinga 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, find 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 satisfied 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.
RIZZI, ROMEO
2011-01-01
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 findinga 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, find 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 satisfied 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.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
