Approximate maximum weight branchings

DOI10.1016/J.IPL.2006.02.011zbMATH Open1184.05058OpenAlexW2004019877MaRDI QIDQ845674FDOQ845674

Authors: Amitabha Bagchi, Ankur Bhargava, Torsten Suel 

Publication date: 29 January 2010

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

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

Recommendations

• Approximating optimum branchings in linear time
• \(k\)-edge subgraph problems
• An efficient algorithm for minimum-weight bibranching
• Finding minimal branchings with a given number of arcs
• The \(b\)-branching problem in digraphs

zbMATH Keywords

analysis of algorithmsgraph algorithms

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Signed and weighted graphs (05C22)

Cites Work

• Title not available (Why is that?)
• Finding optimum branchings
• Edge-disjoint spanning trees and depth-first search
• A note on finding optimum branchings
• A good algorithm for edge-disjoint branching

Cited In (1)

• Approximating optimum branchings in linear time

Uses Software

• zdelta
• GLIMPSE

This page was built for publication: Approximate maximum weight branchings

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