Fully dynamic algorithms for transitive reduction
From MaRDI portal
Cites work
- A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching
- A faster and simpler fully dynamic transitive closure
- A fully dynamic algorithm for maintaining the transitive closure
- A fully dynamic reachability algorithm for directed graphs with an almost linear update time
- A general framework for graph sparsification
- A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
- A rounding by sampling approach to the minimum size \(k\)-arc connected subgraph problem
- A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
- All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time
- Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching
- Approximating the minimum strongly connected subgraph via a matching lower bound
- Better sparsifiers for directed Eulerian graphs
- Computing and Combinatorics
- Computing Minimal Spanning Subgraphs in Linear Time
- Decremental strongly connected components and single-source reachability in near-linear time
- Dynamic low-stretch trees via dynamic low-diameter decompositions
- Dynamic matrix inverse: improved algorithms and matching conditional lower bounds
- Dynamic transitive closure via dynamic matrix inverse (extended abstract)
- Faster algorithms for computing the stationary distribution, simulating random walks, and more
- Finding paths and deleting edges in directed acyclic graphs
- Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs
- Fully dynamic randomized algorithms for graph spanners
- Fully-dynamic graph sparsifiers against an adaptive adversary
- Gaussian elimination is not optimal
- Graph spanners
- Graph sparsification by effective resistances
- High-Probability Parallel Transitive-Closure Algorithms
- scientific article; zbMATH DE number 4083002 (Why is no real title available?)
- scientific article; zbMATH DE number 1256718 (Why is no real title available?)
- Improved Dynamic Reachability Algorithms for Directed Graphs
- Multiplying matrices faster than coppersmith-winograd
- New bounds for matrix multiplication: from alpha to omega
- On fully dynamic graph sparsifiers
- On sparse spanners of weighted graphs
- On the Asymptotic Complexity of Matrix Multiplication
- Optimal decremental connectivity in non-sparse graphs
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
- Randomized approximation schemes for cuts and flows in capacitated graphs
- Roundtrip spanners and roundtrip routing in directed graphs
- Sparsification of directed graphs via cut balance
- Spectral sparsification of graphs
- The Transitive Reduction of a Directed Graph
- Trade-offs for fully dynamic transitive closure on DAGs: breaking through the O ( n 2 barrier
- Transitive compaction in parallel via branchings
This page was built for publication: Fully dynamic algorithms for transitive reduction
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7363180)
