NC Algorithms for Computing a Perfect Matching and a Maximum Flow in One-Crossing-Minor-Free Graphs
From MaRDI portal
Publication:4994988
DOI10.1137/19M1256221zbMath1466.05179arXiv1802.00084OpenAlexW3166103872MaRDI QIDQ4994988
David Eppstein, Vijay V. Vazirani
Publication date: 22 June 2021
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1802.00084
Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parallel algorithms in computer science (68W10) Graph minors (05C83) Flows in graphs (05C21)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The structure of graphs not topologically containing the Wagner graph
- \textsc{max-cut} and containment relations in graphs
- Counting the number of perfect matchings in \(K_{5}\)-free graphs
- The complexity of computing the permanent
- An approach to the subgraph homeomorphism problem
- Random generation of combinatorial structures from a uniform distribution
- Matching is as easy as matrix inversion
- Constructing a perfect matching is in random NC
- NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems
- Characterizing multiterminal flow networks and computing flows in networks of small treewidth
- Diameter and treewidth in minor-closed graph families
- Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors
- A data structure for dynamic trees
- Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
- Drawing trees with perfect angular resolution and polynomial area
- Computing mimicking networks
- On mimicking networks representing minimum terminal cuts
- Über eine Eigenschaft der ebenen Komplexe
- All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs
- A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs (extended abstract)
- Fast Algorithms for Finding Nearest Common Ancestors
- Undirected ST-connectivity in log-space
- An Efficient Parallel Biconnectivity Algorithm
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- Parallel Algorithms in Graph Theory: Planarity Testing
- Fast Parallel Matrix Inversion Algorithms
- Flow in Planar Graphs with Multiple Sources and Sinks
- Flows in One-Crossing-Minor-Free Graphs
- Linear matroid intersection is in quasi-NC
- NC Algorithms for Weighted Planar Perfect Matching and Related Problems
- Planar Maximum Matching: Towards a Parallel Algorithm
- Bipartite Perfect Matching in Pseudo-Deterministic NC
- Planar Graph Perfect Matching Is in NC
- Finding Maximal Sets of Laminar 3-Separators in Planar Graphs in Linear Time
- Succinct Greedy Geometric Routing Using Hyperbolic Geometry
- Paths, Trees, and Flowers
- Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time
- On the Benefit of Merging Suffix Array Intervals for Parallel Pattern Matching
- An excluded minor theorem for the Octahedron plus an edge
- Optimization and Recognition for K 5-minor Free Graphs in Linear Time
- Mimicking Networks and Succinct Representations of Terminal Cuts
- Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces
