Fast algorithms via dynamic-oracle matroids
From MaRDI portal
(Redirected from Fast algorithms via dynamic-oracle matroids)
Cites work
- A constructive arboricity approximation scheme
- A matroid approach to finding edge connectivity and packing arborescences
- A Note on Finding Minimum-Cost Edge-Disjoint Spanning Trees
- Algebraic algorithms for matching and matroid problems
- Algorithms and Data Structures for an Expanded Family of Matroid Intersection Problems
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- An improved cutting plane method for convex optimization, convex-concave games, and its applications
- Applications of Menger's graph theorem
- Breaking the quadratic barrier for matroid intersection
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Computing exact minimum cuts without knowing the graph
- Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
- Dynamic graph connectivity in polylogarithmic worst case time
- Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and \(O(n^{1/2-\epsilon})\)-time
- Edge-disjoint spanning trees and depth-first search
- Forests, frames, and games: Algorithms for matroid sums and applications
- Fully-dynamic minimum spanning forest with improved worst-case update time
- scientific article; zbMATH DE number 5764856 (Why is no real title available?)
- scientific article; zbMATH DE number 5764893 (Why is no real title available?)
- scientific article; zbMATH DE number 3904590 (Why is no real title available?)
- scientific article; zbMATH DE number 140460 (Why is no real title available?)
- scientific article; zbMATH DE number 140484 (Why is no real title available?)
- scientific article; zbMATH DE number 3534506 (Why is no real title available?)
- scientific article; zbMATH DE number 501471 (Why is no real title available?)
- scientific article; zbMATH DE number 1555984 (Why is no real title available?)
- scientific article; zbMATH DE number 3349645 (Why is no real title available?)
- scientific article; zbMATH DE number 3422402 (Why is no real title available?)
- Improved Bounds for Matroid Partition and Intersection Algorithms
- Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication
- Maintaining α-balanced trees by partial rebuilding
- Making data structures persistent
- Matching Theory for Combinatorial Geometries
- Matroid intersection algorithms
- Minimum cost flows, MDPs, and ℓ 1 -regression in nearly linear time for dense instances
- Negative-weight shortest paths and unit capacity minimum cost flow in \(\tilde{O}(m^{10/7}\log W)\) time (extended abstract)
- New algorithms and lower bounds for all-pairs max-flow in undirected graphs
- On a Class of Matroids Arising From Paths in Graphs
- On the cut dimension of a graph
- Random sampling and greedy sparsification for matroid optimization problems
- Sparsification—a technique for speeding up dynamic graph algorithms
- The Union of Matroids and the Rigidity of Frameworks
- Transversals and matroid partition
- Unit Capacity Maxflow in Almost $m^{4/3}$ Time
- Vertex connectivity in poly-logarithmic max-flows
- Weighted min-cut: sequential, cut-query, and streaming algorithms
Cited in
(5)- Subquadratic submodular maximization with a general matroid constraint
- Faster matroid partition algorithms
- Learning partitions using rank queries
- Deterministic (2/3-)-approximation of matroid intersection using nearly-linear independence-oracle queries
- Interdiction of minimum spanning trees and other matroid bases
This page was built for publication: Fast algorithms via dynamic-oracle matroids
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6499300)
