Priority algorithms for graph optimization problems
Priority algorithms for graph optimization problems
复制标题
图优化问题的优先级算法
DOI：
10.1016/j.tcs.2009.09.033
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
Nazanin Mirmohammadi
中科院分区：
文献类型：
--
作者：
A. Borodin;J. Boyar;Kim S. Larsen;Nazanin Mirmohammadi
我们继续研究的优先级或“贪婪”的算法，在Borodin等人。（2003）[10]以及Davis和Impagliazzo（2009）[12]中扩展到图论问题。图论问题提出了一些建模问题，并不存在于原始的应用Borodin等人。Angelopoulos and Borodin（2002）[3].在Davis和Impagliazzo的工作之后，我们进一步澄清了这些概念。在图论的设置，有几个自然的输入配方为一个给定的问题，我们表明，优先级算法的界限一般取决于输入配方。我们研究了各种图形问题的背景下，任意和限制的优先级模型对应于已知的“贪婪算法”。
We continue the study of priority or “greedy-like” algorithms as initiated in Borodin et al. (2003) [10] and as extended to graph theoretic problems in Davis and Impagliazzo (2009) [12]. Graph theoretic problems pose some modeling problems that did not exist in the original applications of Borodin et al. and Angelopoulos and Borodin (2002) [3]. Following the work of Davis and Impagliazzo, we further clarify these concepts. In the graph theoretic setting, there are several natural input formulations for a given problem and we show that priority algorithm bounds in general depend on the input formulation. We study a variety of graph problems in the context of arbitrary and restricted priority models corresponding to known “greedy algorithms”.