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.
2024
Enumeration
Graph theory
Minimal cut
Binary partition
Dynamic data structure
Amortized analysis
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11562/1146731
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact