Simple greedy algorithms for fundamental multidimensional graph problems

DOI10.4230/LIPICS.ICALP.2017.125MaRDI QIDQ5111457zbMATH OpenOpenAlexFDO

Authors Vittorio Bilò, I. Caragiannis, Angelo Fanelli, Michele Flammini, Gianpiero Monaco

Publication date 27 May 2020

Full work available at URL https://hal.science/hal-02089412

zbMATH Keywords

shortest pathsmatroidsSteiner treesarborescencesmultidimensional graph problems

Mathematics Subject Classification ID

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

Recommendations

• Multi-rooted greedy approximation of directed Steiner trees with applications
• Approximating minimum-cost graph problems with spanning tree edges
• On spanning tree problems with multiple objectives
• scientific article; zbMATH DE number 3891405
• CONSTRUCTING MULTIDIMENSIONAL SPANNER GRAPHS

Cited in

(9)

• Robust min-max (regret) optimization using ordered weighted averaging
• Approximation algorithms for multi-parameter graph optimization problems
• scientific article; zbMATH DE number 6469169 (Why is no real title available?)
• Spanning trees with edge conflicts and wireless connectivity
• Approximating combinatorial optimization problems with the ordered weighted averaging criterion
• Approximation algorithms for _p-shortest path and _p-group Steiner tree
• Polylogarithmic approximations for robust s-t path
• Approximating the shortest path problem with scenarios
• Network design under general wireless interference

This page was built for publication: Simple greedy algorithms for fundamental multidimensional graph problems

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