文章基本信息

标题：Simple Greedy Algorithms for Fundamental Multidimensional Graph Problems
本地全文：下载
作者：Vittorio Bil{\`o ; Ioannis Caragiannis ; Angelo Fanelli 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：80
页码：125:1-125:13
DOI：10.4230/LIPIcs.ICALP.2017.125
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：multidimensional graph problems; matroids; shortest paths; Steiner trees; arborescences