Simple Greedy Algorithms for Fundamental Multidimensional Graph Problems

Vittorio Bilò (), Ioannis Caragiannis (), Angelo Fanelli (), Michele Flammini () and Gianpiero Monaco ()
Additional contact information
Vittorio Bilò: Università del Salento = University of Salento [Lecce]
Ioannis Caragiannis: Department of Computer Engineering and Informatics [Patras] - University of Patras
Angelo Fanelli: CREM - Centre de recherche en économie et management - UNICAEN - Université de Caen Normandie - NU - Normandie Université - UR - Université de Rennes - CNRS - Centre National de la Recherche Scientifique
Michele Flammini: DI - Dipartimento di Informatica [Italy] - UNIVAQ - Università degli Studi dell'Aquila = University of L'Aquila = Université de L'Aquila
Gianpiero Monaco: DI - Dipartimento di Informatica [Italy] - UNIVAQ - Università degli Studi dell'Aquila = University of L'Aquila = Université de L'Aquila

Post-Print from HAL

Abstract: We revisit fundamental problems in undirected and directed graphs, such as the problems of computing spanning trees, shortest paths, steiner trees, and spanning arborescences of minimum cost. We assume that there are d different cost functions associated with the edges of the input graph and seek for solutions to the resulting multidimensional graph problems so that the p - norm of the different costs of the solution is minimized. We present combinatorial algorithms that achieve very good approximations for this objective. The main advantage of our algorithms is their simplicity: they are as simple as classical combinatorial graph algorithms of Dijkstra and Kruskal, or the greedy algorithm for matroids.

Keywords: multidimensional graph problems; matroids; shortest paths; Steiner trees; arborescences (search for similar items in EconPapers)
Date: 2017
Note: View the original document on HAL open archive server: https://hal.science/hal-02089412v1
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Published in Dagstuhl Reports, 2017, 80 (125), pp.1-13. ⟨10.4230/LIPIcs.ICALP.2017.125⟩

Downloads: (external link)
https://hal.science/hal-02089412v1/document (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:journl:hal-02089412

DOI: 10.4230/LIPIcs.ICALP.2017.125

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD ().