WorksMathematics
Upper bounds on all-terminal reliability polynomials in terms of cycle basis lengths
Abstract
Let be a connected multigraph with vertices and edges. The all-terminal reliability polynomial of can be written as where is the cycle rank, each edge fails independently with probability , and are the associated coefficients. A cycle basis, which consists of cycles that form a basis of the cycle space of a graph, is an important tool for characterizing its cycle structure. The structural properties of cycle bases, together with the associated length optimization problems and construction algorithms, have been extensively studied. In this context, Colbourn posed the following open problem, which concerns upper bounds on the reliability coefficients in terms of cycle-basis lengths: For all-terminal reliability, is it true that if has a cycle basis containing cycles of lengths , then ? In this paper, we establish a result that resolves this open problem.
Introduction
Let be a connected multigraph with vertices and edges. Its all-terminal reliability polynomial gives the probability that the spanning subgraph consisting of the operational edges is connected. We assume that all vertices remain operational and that
E-mail addresses: [email protected], [email protected], [email protected], [email protected] each edge fails independently with probability . A cycle is a nonempty closed walk in which no edge is repeated and no vertex is repeated except that the initial and terminal vertices coincide. In particular, a single loop is permitted as a cycle of length 1, and two parallel edges are permitted as a cycle of length 2. When computing vertex degrees, each loop is counted twice. For an edge set , let denote the spanning subgraph obtained by deleting the edges in while retaining all vertices. An edge set is called a deletable edge set if is connected. An edge is called a bridge if is disconnected, and the number of bridges is denoted by . For a nonnegative integer , let , with . For a finite set , the notation denotes its cardinality.
The all-terminal reliability polynomial of the graph is defined by
where the coefficients are uniquely determined by (1). The sequence is called the -sequence of the all-terminal reliability polynomial, with the convention that for . Let denote the graph obtained from by deleting all loops, and let be the set of loops of , with . Since deleting loops does not affect connectivity, remains connected and . It follows from (1) and the uniqueness of the coefficients that the -sequence of is obtained by appending zeros to the -sequence of . In particular, whenever .
Research on upper and lower bounds for the all-terminal reliability polynomial has drawn on shellability, network transformations, coefficient inequalities, and extremal graphs. Ball and Provan [11] exploited the shellable structure of the family of deletable edge sets to derive upper and lower bounds on the all-terminal reliability function, incorporating information on the number of spanning trees and the size and number of minimum cuts. Colbourn and Harms [1] employed linear programming to improve the reliability estimates provided by the Ball–Provan and Lomonosov–Polesskii bounds. Brown et al. [6] investigated the effects of network transformations on the -coefficients of the all-terminal reliability polynomial and established efficiently computable coefficientwise upper and lower bounds, which they incorporated as additional constraints to strengthen the Ball–Provan method. For -sequences arising from graphs, Brown and Colbourn [7] established several non-Stanley-type inequalities, which provide new coefficient constraints for reliability estimation. Brown et al. [8] exploited the connection between chip-firing processes on graphs and reliability -sequences, together with structural information about the corresponding monomial representations, to improve the all-terminal reliability bounds obtained by the Ball–Provan method. For sparse graphs, Romero [14] considered connected simple graphs with prescribed numbers of vertices and edges whose cycle rank is at most 4. Using uniformly least reliable graphs and previously known uniformly most reliable graphs, Romero obtained optimal universal upper and lower bounds on reliability for this class of graphs. Building on earlier results, Colbourn [2] investigated the coefficients of the all-terminal reliability polynomial and posed the following open problem.
Problem 1.1. [2] For all-terminal reliability, is it true that if has a cycle basis containing cycles of lengths , then
Define a cactus graph to be a connected graph in which each edge belongs to at most one cycle, and let denote the field with two elements. We investigate this problem and obtain the following theorem:
Theorem 1.2. Let be an arbitrary cycle basis of over , and let denote the length of . Then, for every , the coefficients in (1) satisfy
Where, equality holds in the second inequality simultaneously for all if and only if is a cactus graph.
Remark. For , equality holds in the first inequality if and only if the connected multigraph obtained from by deleting all loops has cycle rank at most . For , we have . In particular, if is loopless, then the first inequality is strict throughout the stated range.
Brown and Colbourn [7], in their study of upper and lower bounds on network reliability, used an expansion of the all-terminal reliability polynomial according to the size of the failed edge set, namely the -form. Huh [9] also used this representation in studying the log-concavity of matroid -vectors and its applications to network reliability. Thus, (1) can be rewritten as follows:
Here, is the number of deletable edge sets containing edges, and for . For example, , is the number of non-bridge edges in , and is the number of spanning trees of . A spanning tree is a connected acyclic subgraph that contains all vertices and has one fewer edge than vertices; let denote the number of spanning trees of . From (1) and (3), we obtain
The above discussion and Theorem 1.2 yield the following result.
Corollary 1.1. Under the assumptions of Theorem 1.2, for every , we have
Equality always holds when ; for each , equality holds if and only if is a cactus graph.
In particular, setting in (4) yields
with equality if and only if is a cactus graph.
Remark. Bortoletto et al. [3] previously established (5) in their study of the geometric structure of periodic timetables.
The paper is organized as follows. Section 2 introduces cycle spaces, independent sets of matroids, and the associated quotient algebras, and presents the lemmas that are needed for the subsequent proofs. In Section 3, we establish upper bounds on the coefficients of the all-terminal reliability polynomial in terms of the lengths of the cycles in an arbitrary binary cycle basis, from which we further derive upper bounds on the numbers of deletable edge sets and spanning trees. Section 4 summarizes the main results and poses further related questions.
Preliminaries
In this section, we retain the notation introduced in Section 1 and present the definitions and lemmas that are needed to prove the main theorem.
Let and denote linear span and vector space dimension over the field , respectively. Let denote the vector space over whose coordinates are indexed by the edge set . For any , let denote the characteristic vector of , whose coordinate at an edge is given by
Fix a spanning tree of . For each non-tree edge , let denote the fundamental cycle associated with with respect to . If is not a loop, then consists of together with the unique path in joining its endpoints; if is a loop, then is the cycle of length 1 consisting solely of .
We next introduce the binary cycle space and its basic properties, and describe a matching between the cycles in a cycle basis and the non-tree edges of a spanning tree.
Definition 2.1. [16] The binary cycle space of is defined by
where denotes the characteristic vector of the edge set of .
A family of cycles is called a binary cycle basis of if the corresponding vectors form a basis of .
Since the only cycle that contains a given loop is the cycle consisting of that loop alone, every binary cycle basis must contain the cycle of length 1 formed by each loop. Removing these cycles leaves a binary cycle basis of the loopless graph .
Lemma 2.1. [16] The dimension of the binary cycle space of a connected graph equals its cycle rank, that is,
Moreover, for any spanning tree of , the characteristic vectors of the fundamental cycles with respect to form a basis of the binary cycle space.
Lemma 2.2. [12] Let be such that is a spanning tree and let be a binary cycle basis of . Then a bijection
To establish the connection between the deletable edge sets of a graph and its cographic matroid, we introduce the basic notions of matroids, including independent sets, bases, and rank.
Definition 2.2. [10] A matroid is an ordered pair consisting of a finite set and a collection of subsets of having the following three properties:
(i) ;
(ii) If and , then ;
(iii) If and are in and , then there is an element of such that .
We shall call (i) and (ii) the hereditary and independence augmentation properties. The members of are the independent sets of , and is the ground set of . We shall often write for and for , particularly. A subset of that is not in is called dependent.
We call a maximal independent set in a basis or a base of .
Lemma 2.3. [10] If and are bases of a matroid , then .
All bases of a matroid have the same size; this common size is called the rank of and is denoted by .
Let be a finite set, and let be a nonempty family of subsets of . We call a simplicial complex on if whenever and . Each member of is called a face. By axioms (i) and (ii) of Definition 2.2, contains and is closed under taking subsets. Thus, is a simplicial complex, which is called the independence complex of the matroid .
To study the coefficients using algebraic methods, we introduce a graded quotient algebra associated with .
Definition 2.3.[5] Let , where each variable has degree 1. For any , write , with . A monomial is called squarefree if the exponent of each variable is either 0 or 1. Define
Both and are homogeneous ideals. Define the graded quotient algebra
where is the homogeneous component of degree . Let denote the image of in the quotient algebra, and write , with .
Fix a binary cycle basis of . Since form a basis of the binary cycle space of , we have
In particular, . If is a bridge of , then is disconnected, so and hence .
Let denote the graphic matroid of , whose independent sets are the edge sets that contain no cycles. Since is connected, the bases of are precisely the edge sets of the spanning trees of . Its dual matroid is called the cographic matroid of , whose bases are the complements of the edge sets of the spanning trees of . Consequently, .
By axiom (ii) of Definition 2.2, every subset of a basis is independent. Moreover, since the ground set is finite, every independent set can be extended to a basis. Thus, an edge set is independent in if and only if it is contained in a basis. For any , we have
Therefore, the independent sets of are precisely the deletable edge sets of , and its independence complex is . The graded quotient ring is called the Stanley–Reisner ring of the independence complex of the cographic matroid . Define by
The coefficient vector is called the -vector of .
Lemma 2.4. [5] Let be a spanning tree of , and set
Then the quotient algebra admits the graded decomposition
where denotes the ideal generated by the images of the linear forms in in , and denotes the homogeneous component of degree of , namely, the vector space consisting of the images of all homogeneous polynomials of degree in this quotient algebra. The dimensions of these homogeneous components form the -vector of ; that is, .
Since the bases of are the complements of the edge sets of spanning trees, its independent sets are precisely the deletable edge sets. Hence, for each , there are exactly independent sets of cardinality . By (1), (3), and the identity , we obtain
(8) also gives
Therefore, . Comparing coefficients yields for every . Thus, is precisely the -vector of the independence complex of .
Lemma 2.5. [5] The images of the squarefree monomials in the quotient algebra span this algebra.
When is loopless, the assertion follows directly from [5]. If contains loops, then each loop forms a cycle by itself, so and hence . Since deleting loops does not affect the connectivity of , we have . Applying Lemma 2.5 to therefore yields the desired spanning result for .
To identify the indices for which is positive or zero, we state the following result on the -vector of a matroid independence complex.
Lemma 2.6. [7] Let be a finite matroid of rank whose independence complex has -vector . If has exactly elements that belong to every basis, then
We next recall the third isomorphism theorem for rings, which will be used to handle successive quotients.
Lemma 2.7. [4] Let be an associative ring, and let , be two-sided ideals of with . Then is a two-sided ideal of the quotient ring , and the map
is a ring isomorphism. Consequently, .
We next relate the quotient algebra defined above to the coefficients and identify these coefficients with the dimensions of its homogeneous components.
Lemma 2.8. For every , we have
and
Proof. First, since the independent sets of are precisely the deletable edge sets of , for any we have if and only if is disconnected. Thus, the Stanley–Reisner ideal of the independence complex of is
Consequently, .
Next, fix a spanning tree of . Let , so that . Let denote the ideal generated by the linear forms in in the polynomial ring . We now show that .
We first prove that . Let be an arbitrary cycle of . Since the characteristic vectors of the fundamental cycles form a basis of the binary cycle space, there exist coefficients such that
For any , comparing the coordinates indexed by on both sides yields
Since when and otherwise, we have
Combining (9) and (10), we obtain . Each belongs to , which is closed under addition and multiplication by elements of . Hence, the above linear
combination also belongs to , and therefore . Since is arbitrary, contains the linear form associated with every cycle of . As is precisely the ideal generated by all these linear forms, we conclude that .
Conversely, every fundamental cycle is itself a cycle of . Since is the ideal generated by the linear forms associated with all cycles of , we have for every non-tree edge . Thus, all linear forms in belong to . Since is an ideal, it also contains all polynomial multiples of these linear forms and all finite sums of such multiples. By the definition of as the ideal generated by the linear forms in in the polynomial ring , it follows that .
Combining the two inclusions yields .
Next, let denote the ideal in generated by the images of the linear forms in . Since every element of maps to zero in the quotient ring, adding an element of to an element of does not change its image. Hence, . Therefore, by Lemma 2.7 and (6), we have
By Lemma 2.4, it follows that
For , we have and , so .
Finally, we prove the spanning assertion for each homogeneous component. For , let be arbitrary. By Lemma 2.5, there exist coefficients such that . Since is a homogeneous ideal, is a graded algebra in which each is homogeneous of degree . Taking the homogeneous component of degree on both sides yields . If is disconnected, then and hence . Omitting these zero terms, we obtain
Therefore, . Conversely, each in this set belongs to , so their span is also contained in ; that is, $\mathcal{A}(G)_i\supseteq\operatorname{span}_{\mathbb{Z}_2}{\bar{x}^S:S\subseteq E(G),,|S|=i,,G-S\text{ is connected}}. Thus,
If is connected, then it has at least edges, so and hence . Thus, when , there is no deletable edge set of cardinality , and the set of monomials in the spanning expression above is empty. Since the span of the empty set is the zero space, we obtain . ∴
To estimate the dimensions of higher-degree homogeneous components using dimension bounds for the degree-one subspaces associated with the cycles in a cycle basis, we state two standard dimension estimates for products and sums of subspaces. Inequality (11) follows directly from the tensor product basis theorem in [15], while (12) follows from the dimension estimate for sums of subspaces in [13].
Lemma 2.9. Let be a nonzero unital commutative graded algebra over a field , let be a nonnegative integer, and let be finite-dimensional subspaces. Denote by the -vector space spanned by all products with . Then
If is a finite family of finite-dimensional subspaces of a common -vector space, then
By convention, the empty product space for is , and the sum of an empty family of subspaces is . The empty numerical product and sum are taken to be and , respectively.
Proof of Theorem 1.2
Proof of Theorem 1.2. By Lemma 2.8, for every , we have . Moreover, is spanned by the squarefree monomials for which and is connected. Thus, to prove (2), it suffices to show that
To this end, we first match the edges of each deletable edge set to distinct cycles in the given cycle basis and then show that the corresponding monomial lies in the product space determined by these cycles.
We first show that, for every deletable edge set , there exists an injection
If , the empty map suffices. Henceforth, assume that . Since is connected, choose a spanning tree of . Because all vertices are retained when edges are deleted, is also a spanning tree of . Moreover, , so . By Lemma 2.2, there exists a bijection
For each , define whenever . Since , each determines a unique index . The injectivity of implies that is also injective. For every , we have .
Next, for each , define
The space is spanned by the images of the edge variables corresponding to the edges of . By (7), we have , so in the quotient algebra. Since is nonempty, choose any edge . Over the field , we have , which expresses as a linear combination of the images of the remaining edge variables. Thus, removing from the spanning family leaves a family that still spans ; that is,
Since every vector in can be expressed as a linear combination of these vectors, the dimension of is at most ; that is,
In particular, when , the cycle consists of a single loop, so and (13) remains valid.
Next, for each , let
By Lemma 2.9 and (13), we obtain
We now prove that .
We first show that . Let be a nonempty deletable edge set of cardinality . There exists an injection such that for every . Set , so that induces a bijection between and . For each , let be the unique edge for which , and set . Since , we have . Thus, the product is formed by choosing one element from each . By the definition , we obtain . When , we take , and then , so the assertion remains valid. By Lemma 2.8, is spanned by all monomials for which and is connected. Each such monomial belongs to some with . Consequently, every element of belongs to the sum of these subspaces, which gives .
We next prove that . Since is a graded quotient algebra, its multiplication satisfies for all . Write , where . For each , choose an arbitrary . Since , repeated application of the multiplication property yields
Every element of is a linear combination of products of the form , so . When , we have , so the assertion remains valid. Since each with is contained in , their sum is also contained in . Hence,
Combining the two inclusions, we obtain
Finally, applying Lemmas 2.8 and 2.9, together with (14) and (15), yields
Since is nonnegative, we conclude that
where .
We now show that equality holds in the second inequality in (2) simultaneously for all if and only if is a cactus graph. We first prove necessity. Suppose that for every . If , then is a tree and hence a cactus graph. Henceforth, assume that . Taking gives . Using and , we obtain
First, we show that the union of the edge sets of the basis cycles is precisely the set of all non-bridge edges of . Let be an arbitrary non-bridge edge of . If is a loop, then it forms a cycle by itself. Otherwise, since is connected, there exists a simple path between the endpoints of that avoids . This path, together with , forms a cycle . Since the characteristic vectors of the cycles in span the binary cycle space, there exist such that
Suppose that belongs to none of the basis cycles. Then for every , and hence
This contradicts , which holds because . Thus, belongs to at least one basis cycle. Since was arbitrary, every non-bridge edge belongs to at least one basis cycle.
Choose any edge of a fundamental cycle. If it is a self-loop, deleting it does not affect connectivity; otherwise, after its deletion, its endpoints remain connected via the remaining edges of the cycle. Thus, deleting any edge of a basis cycle leaves connected, so every edge of a basis cycle is a non-bridge edge.
Thus, the union of the edge sets of the basis cycles is precisely the set of all non-bridge edges of , so
Combining with (16), we obtain
Here, counts the edges separately for each basis cycle, whereas counts each edge in the union exactly once. If two basis cycles share an edge, then that edge is counted at least twice in but only once in . Every other edge in the union is counted at least once in the former expression, so , which contradicts the equality above. Therefore, the edge sets of are pairwise disjoint.
Let be an arbitrary cycle of . Since is a binary cycle basis, the edge set of can be expressed as the symmetric difference of the edge sets of some basis cycles. Since these edge sets are pairwise disjoint, each edge occurs exactly once among the selected cycles. Hence, their symmetric difference coincides with their union.
We next show that only one basis cycle can be selected. Suppose that at least two basis cycles are selected. If the selected cycles are pairwise vertex-disjoint, then the subgraph they form is disconnected, which contradicts the connectedness of . Otherwise, two selected cycles share a vertex, at which each cycle contributes degree 2, with a loop contributing 2 to the degree of its vertex. Since these two cycles have disjoint edge sets, their union has degree 4 at the shared vertex. The subgraph formed by all selected cycles therefore has degree at least 4 at that vertex, which contradicts the fact that every vertex of has degree 2. Thus, at most one basis cycle can be selected. Since is nonempty, exactly one is selected, so for some . As was arbitrary, the cycles of are precisely . Their edge sets are pairwise disjoint, so every edge of belongs to at most one cycle. Therefore, is a cactus graph.
We next prove sufficiency. Suppose that is a cactus graph. Then the edge sets of all its cycles are pairwise disjoint, so their characteristic vectors are linearly independent. Since these vectors also span the binary cycle space of , they form a basis of this space. As the binary cycle space has dimension , the graph has exactly cycles. Thus, the binary cycle basis consists of all the cycles of . Since every non-bridge edge belongs to a cycle and no bridge belongs to any cycle, is the disjoint union of the set of bridges and the edge sets of . Using and , we obtain
Delete an arbitrary edge from each and retain all bridges. Deleting a loop does not affect connectivity. For each deleted non-loop edge, its endpoints remain connected by the remaining edges of the cycle containing it. Since the cycles have pairwise disjoint edge sets, none of these remaining edges has been deleted, so the resulting spanning subgraph is connected. Moreover, exactly distinct edges have been deleted, leaving a spanning subgraph with vertices and edges. Hence, this subgraph is a spanning tree of . Conversely, every spanning tree is acyclic and therefore omits at least one edge from each . Since the complement of its edge set contains exactly edges and the cycles have pairwise disjoint edge sets, exactly one edge is deleted from each cycle, and all bridges are retained. Thus, the spanning trees of are precisely the spanning subgraphs obtained by deleting one edge from each and retaining all bridges.
It follows that the spanning subgraph consisting of the operational edges is connected if and only if all bridges are operational and at most one edge fails in each . Indeed, if the spanning subgraph consisting of the operational edges is connected, then it contains a spanning tree. All failed edges lie in the complement of the edge set of this tree, so no bridge has failed, and each contains at most one failed edge. Conversely, suppose that all bridges are operational and each contains at most one failed edge. In each cycle containing a failed edge, select that edge; in each cycle containing no failed edge, select an arbitrary edge. Deleting the selected edges yields a spanning tree, all of whose edges are operational. Therefore, the spanning subgraph consisting of the operational edges is connected.
The probability that all bridges are operational is . For each , the probability that no edge fails is , and the probability that exactly one edge fails is . When , the condition that at most one edge fails is always satisfied, and its probability is , which is consistent with the fact that loops do not affect connectivity. Since edges fail independently, and the set of bridges and the edge sets of the cycles are pairwise disjoint, we have
Comparing this with (1) gives . Expanding the product and comparing the coefficients of , we obtain
When , all empty products are taken to be 1, so the conclusion remains valid.
We next show that, for , equality holds in the first inequality if and only if the connected multigraph obtained from by deleting all loops has cycle rank at most , and that for . In particular, if is loopless, then the first inequality is strict throughout the stated range.
Since the bases of are precisely the complements of the edge sets of spanning trees of , an element belongs to every basis of if and only if the corresponding edge belongs to no spanning tree of . No loop belongs to a spanning tree, whereas every non-loop edge is contained in some spanning tree. Thus, has exactly elements that belong to every basis.
Since and is the -vector of the independence complex of , Lemma 2.6 yields
The graph obtained by deleting all loops from remains connected and has cycle rank
Therefore, for , equality holds in the first inequality if and only if deleting all loops from leaves a connected multigraph of cycle rank at most ; for , we have . In particular, if is loopless, then , so the first inequality is strict for every .
Proof of Corollary 1.1. Set . Substitute into (1) and (3), and multiply both identities by . Using , we obtain
Furthermore, we have
Comparing the coefficients of on both sides yields
Therefore, .
Since by Theorem 1.2. For , both sides of the asserted bound equal 1. For , equality forces , because all summands above are nonnegative and . The equality argument in the proof of Theorem 1.2 then implies that is a cactus graph.
Conversely, for a cactus graph Theorem 1.2 gives for every , so equality holds for every .
In particular, setting and using yields . When , apply the equality characterization for above with . When , is a tree, , and the empty product is , so the conclusion also holds.
Conclusion
Using a quotient algebra representation associated with the cographic matroid, we establish upper bounds on the coefficients of the all-terminal reliability polynomial in terms of the lengths of the cycles in an arbitrary binary cycle basis, thereby providing an affirmative answer to the aforementioned question for binary cycle bases. Through the coefficient transformation relating and , we further derive upper bounds on the numbers of deletable edge sets and spanning trees. We also prove that the upper bounds on are attained simultaneously for all if and only if is a cactus graph. The bounds obtained in this paper depend only on the lengths of the cycles in a cycle basis. Several questions remain for further investigation. How can the number and distribution of edges shared by cycles in a cycle basis be used to obtain sharper upper bounds on the coefficients ? How can the lengths of the basis cycles and the cutset structure of the graph be used together to improve estimates for the numbers of deletable edge sets and spanning trees? When edges have different failure probabilities, how can the upper bounds on reliability obtained by the cycle-basis method be further sharpened?
Conflicts of Interest:
The authors declare that they have no conflicts of interest.
Data availability statement:
No data were used to support this study.
References
- [1]C.J. Colbourn, D.D. Harms, Bounding all-terminal reliability in computer networks, Networks 18 (1988) 1–12.DOI
- [2]C.J. Colbourn, Some open problems on reliability polynomials, Congr. Numer. 93 (1993) 187–202.
- [3]E. Bortoletto, N. Lindner, B. Masing, The tropical and zonotopal geometry of periodic timetables, Discrete Comput. Geom. 73 (2025) 719–763.
- [4]E. Noether, Abstrakter Aufbau der Idealtheorie in algebraischen Zahl- und Funktionenkörpern, Math. Ann. 96 (1927) 26–61.DOI
- [5]J.I. Brown, C.J. Colbourn, D.G. Wagner, Cohen–Macaulay rings in network reliability, SIAM J. Discrete Math. 9 (1996) 377–392.DOI
- [6]J.I. Brown, C.J. Colbourn, J.S. Devitt, Network transformations and bounding network reliability, Networks 23 (1993) 1–17.DOI
- [7]J.I. Brown, C.J. Colbourn, Non-Stanley bounds for network reliability, J. Algebraic Combin. 5 (1996) 13–36.DOI
- [8]J.I. Brown, C.J. Colbourn, R.J. Nowakowski, Chip firing and all-terminal network reliability bounds, Discrete Optim. 6 (2009) 436–445.DOI
- [9]J. Huh, h-Vectors of matroids and logarithmic concavity, Adv. Math. 270 (2015) 49–59.arxiv.org/abs/1201.2915
- [10]J. Oxley, Matroid Theory, second ed., Oxford Graduate Texts in Mathematics, vol. 21, Oxford University Press, Oxford, 2011.
- [11]M.O. Ball, J.S. Provan, Bounds on the reliability polynomial for shellable independence systems, SIAM J. Algebraic Discrete Methods 3 (1982) 166–181.DOI
- [12]M. van der Meulen, Reconfiguring Electricity Distribution Networks to Minimize Power Loss: NP-hardness and Efficient Approximation Algorithms, Master’s thesis, Radboud University, 2015.
- [13]N. Bourbaki, Algebra I: Chapters 1–3, Elements of Mathematics, Springer-Verlag, Berlin, 1989.
- [14]P. Romero, Universal reliability bounds for sparse networks, IEEE Trans. Reliab. 71 (2022) 359–369.DOI
- [15]S. Lang, Algebra, revised third ed., Graduate Texts in Mathematics, vol. 211, Springer-Verlag, New York, 2002.
- [16]T. Kavitha, C. Liebchen, K. Mehlhorn, D. Michail, R. Rizzi, T. Ueckerdt, K.A. Zweig, Cycle bases in graphs: Characterization, algorithms, complexity, and applications, Comput. Sci. Rev. 3 (2009) 199–243.DOI