Listing the bonds of a graph in \(\widetilde{O} (n)\)-delay
From MaRDI portal
Publication:6124426
DOI10.1016/j.dam.2024.01.004MaRDI QIDQ6124426
Alice Raffaele, Takeaki Uno, Romeo Rizzi
Publication date: 27 March 2024
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Applications of graph theory (05C90) Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Connectivity (05C40)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Lower bounds for fully dynamic connectivity problems in graphs
- Complexity models for incremental computation
- Tight lower bounds for the number of inclusion-minimal \(st\)-cuts
- A data structure for dynamic trees
- Computing the largest bond and the maximum connected cut of a graph
- Graph Theory
- Maintaining information in fully dynamic trees with top trees
- Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time
- Randomized fully dynamic graph algorithms with polylogarithmic time per operation
- Near-optimal fully-dynamic graph connectivity
- An Algorithm to Enumerate All Cutsets of a Graph in Linear Time per Cutset
- Determination of All Minimal Cut-Sets between a Vertex Pair in an Undirected Graph
- A Gaussian Elimination Algorithm for the Enumeration of Cut Sets in a Graph
- Enumeration of All Minimal Cut-Sets for a Node Pair in a Graph
- Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees
- Minimizing diameters of dynamic trees
- The complexity of satisfiability problems
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
- An Implicit Enumeration Scheme for Proper Cut Generation
- Network reliability analysis: Part I
- Faster Deterministic Fully-Dynamic Graph Connectivity
- Encyclopedia of Algorithms
