Linear Time Approximation Algorithms for Degree Constrained Subgraph Problems
From MaRDI portal
Publication:2971609
DOI10.1007/978-3-540-76796-1_9zbMath1359.90119OpenAlexW2189595797MaRDI QIDQ2971609
Publication date: 7 April 2017
Published in: Research Trends in Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-76796-1_9
Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
A 2/3-Approximation Algorithm for Vertex Weighted Matching in Bipartite Graphs, On two-machine flow shop scheduling, Greedy matching: guarantees and limitations, Approximation algorithms in combinatorial scientific computing, Efficient Approximation Algorithms for Weighted $b$-Matching
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximating optimum branchings in linear time
- A simple approximation algorithm for the weighted matching problem
- Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
- Another look at the degree constrained subgraph problem
- Approximating matchings in parallel
- A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm
- Maximizing the number of unused colors in the vertex coloring problem
- Maximum skew-symmetric flows and matchings
- Clique partitions, graph compression and speeding-up algorithms
- A simpler linear time \( \frac{2}{3} - \varepsilon\) approximation for maximum weight matching
- Matching algorithms are fast in sparse random graphs
- Maximum network flow with floating point arithmetic.
- A linear-time approximation algorithm for weighted matchings in graphs
- Maximal Flow Through a Network
- TWO THEOREMS IN GRAPH THEORY
- Algorithms for two bottleneck optimization problems
- An Analysis of the Greedy Heuristic for Independence Systems
- Parallel Multilevel series k-Way Partitioning Scheme for Irregular Graphs
- Faster scaling algorithms for general graph matching problems
- Average-case analysis of algorithms for matchings and related problems
- Computing Minimum-Weight Perfect Matchings
- On Kuhn's Hungarian Method?A tribute from Hungary
- Balanced network flows. VIII. A revised theory of phase‐ordered algorithms and the O( $\bf\it\sqrt{n}m$ log(n2/m)/log n) bound for the nonbipartite cardinality matching problem
- Paths, Trees, and Flowers
- Greedy in Approximation Algorithms
- Implementation of O ( nm log n ) weighted matchings in general graphs
- Algorithms – ESA 2004
- Optimum branchings
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
