Approximating optimum branchings in linear time

DOI10.1016/j.ipl.2008.09.022zbMath1191.68879OpenAlexW2003027801MaRDI QIDQ976065

Valentin Ziegler

Publication date: 16 June 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2008.09.022

zbMATH Keywords

graph algorithmapproximation algorithmbranching

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (1)

Linear Time Approximation Algorithms for Degree Constrained Subgraph Problems

Cites Work

• Unnamed Item
• Unnamed Item
• Approximate maximum weight branchings
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• Combinatorial optimization. Theory and applications.
• Optimum branchings
• A simple derivation of edmonds' algorithm for optimum branchings

This page was built for publication: Approximating optimum branchings in linear time