Given a connected graph G = (V, E), with n := |V| vertices and m := |E| edges, a cut can be represented as a bipartition {S, S} of the vertices or as the set of those edges in E having one endpoint in S and the other in S, denoted by 8G(S, S). A cut is minimal, or also called bond, if and only if the two induced subgraphs obtained by removing the edges in the cut are both connected. When the bond separates two given vertices s and t, we talk about s, t-bond. In this work, we consider the problems of listing all the bonds and listing all the s, t-bonds in a graph. These fundamental problems find application in many research areas, such as, beyond graph theory, network reliability, bioinformatics, and chemistry. The state-of-the-art algorithm exploits binary partition to output each s, t-bond in O(m) per bond, being thus classified as an O(m)-delay algorithm. Here we present two new algorithms to address these problems. The first one implements a slightly different branching strategy than the state of the art, though achieving the same complexity. Anyway, we can improve it by relying on dynamic data structures and amortized analysis, obtaining an algorithm that outputs a new bond in O similar to(n). By assuming only the two bond-shores are output for every bond, this is the first outputlinear algorithm listing bonds. In case we commit to explicitly providing the entire edge-set of every bond, the delay becomes O similar to(n) + |8G(S, S)|. (c) 2024 Elsevier B.V. All rights reserved.
Listing the bonds of a graph in O˜(n)–delay
Alice Raffaele;Romeo Rizzi;
2024-01-01
Abstract
Given a connected graph G = (V, E), with n := |V| vertices and m := |E| edges, a cut can be represented as a bipartition {S, S} of the vertices or as the set of those edges in E having one endpoint in S and the other in S, denoted by 8G(S, S). A cut is minimal, or also called bond, if and only if the two induced subgraphs obtained by removing the edges in the cut are both connected. When the bond separates two given vertices s and t, we talk about s, t-bond. In this work, we consider the problems of listing all the bonds and listing all the s, t-bonds in a graph. These fundamental problems find application in many research areas, such as, beyond graph theory, network reliability, bioinformatics, and chemistry. The state-of-the-art algorithm exploits binary partition to output each s, t-bond in O(m) per bond, being thus classified as an O(m)-delay algorithm. Here we present two new algorithms to address these problems. The first one implements a slightly different branching strategy than the state of the art, though achieving the same complexity. Anyway, we can improve it by relying on dynamic data structures and amortized analysis, obtaining an algorithm that outputs a new bond in O similar to(n). By assuming only the two bond-shores are output for every bond, this is the first outputlinear algorithm listing bonds. In case we commit to explicitly providing the entire edge-set of every bond, the delay becomes O similar to(n) + |8G(S, S)|. (c) 2024 Elsevier B.V. All rights reserved.File | Dimensione | Formato | |
---|---|---|---|
listing_bonds_with_Takeaky_and_Alice2024.pdf
solo utenti autorizzati
Licenza:
Accesso ristretto
Dimensione
538.38 kB
Formato
Adobe PDF
|
538.38 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.