A matroid approach to finding edge connectivity and packing arborescences
From MaRDI portal
Publication:1892220
DOI10.1006/jcss.1995.1022zbMath0827.68087OpenAlexW4247278211MaRDI QIDQ1892220
Publication date: 8 June 1995
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/2faa34cebd5b93601b85cd1f33010ea289660ab2
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Approximation algorithms for aligning points, A new probabilistic analysis of Karger's randomized algorithm for minimum cut problems, Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time, Optimal per-edge processing times in the semi-streaming model, An algorithm for minimum cost arc-connectivity orientations, Reachability in arborescence packings, An optimal rounding for half-integral weighted minimum strongly connected spanning subgraph, Computing pure Nash and strong equilibria in bottleneck congestion games, Sensitivity Analysis for Convex Separable Optimization Over Integral Polymatroids, Simple planar graph partition into three forests, An ETH-tight algorithm for bidirected Steiner connectivity, Intractability of min- and max-cut in streaming graphs, Relay placement for fault tolerance in wireless networks in higher dimensions, Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths, Finding strong bridges and strong articulation points in linear time, Computation and efficiency of potential function minimizers of combinatorial congestion games, Efficient and Adaptive Parameterized Algorithms on Modular Decompositions, Compact cactus representations of all non-trivial min-cuts, Independent spanning trees with small depths in iterated line digraphs, Unnamed Item, Disjoint paths in arborescences, A simple primal-dual approximation algorithm for 2-edge-connected spanning subgraphs, A linear-time algorithm to find a pair of arc-disjoint spanning in-arborescence and out-arborescence in a directed acyclic graph, Minimum Cuts of Simple Graphs in Almost Always Linear Time, A binomial approximation method for the Ising model, Fast exact algorithms for survivable network design with uniform requirements, The Minimum Weight In-Tree Cover Problem, Random sampling and greedy sparsification for matroid optimization problems, Sparse hypergraphs and pebble game algorithms, Sparsity-certifying graph decompositions, Unnamed Item, I/O efficient algorithms for the minimum cut problem on unweighted undirected graphs, Orientations and detachments of graphs with prescribed degrees and connectivity, Relay placement for two-connectivity, Linear time algorithms for graph search and connectivity determination on complement graphs.
