Approximating optimum branchings in linear time

DOI10.1016/J.IPL.2008.09.022MaRDI QIDQ976065zbMATH OpenOpenAlexFDO

Authors V. 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

approximation algorithmbranchinggraph algorithm

Mathematics Subject Classification ID

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

Recommendations

• Approximate maximum weight branchings
• Linear-time approximation for maximum weight matching
• Linear time approximation algorithms for~degree~constrained subgraph problems
• An efficient algorithm for minimum-weight bibranching
• Approximating Maximum Leaf Spanning Trees in Almost Linear Time

Cites work

• scientific article; zbMATH DE number 3285076 (Why is no real title available?)
• scientific article; zbMATH DE number 3373559 (Why is no real title available?)
• A simple derivation of edmonds' algorithm for optimum branchings
• Approximate maximum weight branchings
• Combinatorial optimization. Theory and applications.
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• Optimum branchings

Cited in

(7)

• Linear time approximation algorithms for~degree~constrained subgraph problems
• Constructive linear time algorithms for branchwidth
• Approximate maximum weight branchings
• Super-polynomial approximation branching algorithms
• Effective branching splitting method under cost constraint
• Branching of solutions of linear time-optimal problem at an irregular point
• Optimal procedures and complexity analyses of nonserial converging branch networks

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q976065)