Linear Time Approximation Algorithms for Degree Constrained Subgraph Problems (Q2971609)

From MaRDI portal

Jump to:navigation, search

scientific article

Language	Label	Description	Also known as
English	Linear Time Approximation Algorithms for Degree Constrained Subgraph Problems	scientific article

Statements

scholarly article

0 references

Linear Time Approximation Algorithms for Degree Constrained Subgraph Problems (English)

0 references

Stefan Hougardy

0 references

Research Trends in Combinatorial Optimization

0 references

publication date

7 April 2017

0 references

describes a project that uses

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1007/978-3-540-76796-1_9

0 references

0 references

A linear-time approximation algorithm for weighted matchings in graphs

0 references

A simpler linear time \( \frac{2}{3} - \varepsilon\) approximation for maximum weight matching

0 references

An Analysis of the Greedy Heuristic for Independence Systems

0 references

Balanced network flows. VIII. A revised theory of phase‐ordered algorithms and the <i>O</i>( $\bf\it\sqrt{n}m$ log(<i>n</i><sup>2</sup>/<i>m</i>)/log <i>n</i>) bound for the nonbipartite cardinality matching problem

0 references

0 references

An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

0 references

Efficient algorithms for finding minimum spanning trees in undirected and directed graphs

0 references

Implementation of <i>O</i> ( <i>nm</i> log <i>n</i> ) weighted matchings in general graphs

0 references

Maximal Flow Through a Network

0 references

Algorithms for two bottleneck optimization problems

0 references

Computing Minimum-Weight Perfect Matchings

0 references

Another look at the degree constrained subgraph problem

0 references

A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm

0 references

0 references

0 references

0 references

Paths, Trees, and Flowers

0 references

A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

0 references

Faster scaling algorithms for general graph matching problems

0 references

Matching algorithms are fast in sparse random graphs

0 references

Average-case analysis of algorithms for matchings and related problems

0 references

TWO THEOREMS IN GRAPH THEORY

0 references

Algorithms – ESA 2004

0 references

Approximating matchings in parallel

0 references

Parallel Multilevel series k-Way Partitioning Scheme for Irregular Graphs

0 references

Clique partitions, graph compression and speeding-up algorithms

0 references

On Kuhn's Hungarian Method?A tribute from Hungary

0 references

Maximizing the number of unused colors in the vertex coloring problem

0 references

0 references

Maximum network flow with floating point arithmetic.

0 references

Optimum branchings

0 references

A simple approximation algorithm for the weighted matching problem

0 references

0 references

Maximum skew-symmetric flows and matchings

0 references

0 references

Greedy in Approximation Algorithms

0 references

Approximating optimum branchings in linear time

0 references

Identifiers

zbMATH Open document ID

0 references

10.1007/978-3-540-76796-1_9

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

zbMATH DE Number

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:2971609

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Item:Q2971609&oldid=36314825"