کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10331985 | 687011 | 2005 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A greedy approach to compute a minimum cycle basis of a directed graph
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: A greedy approach to compute a minimum cycle basis of a directed graph A greedy approach to compute a minimum cycle basis of a directed graph](/preview/png/10331985.png)
چکیده انگلیسی
We consider the problem of computing a minimum cycle basis of a directed graph with m arcs and n nodes. We adapt the greedy approach proposed by Horton [A polynomial-time algorithm to find the shortest cycle basis of a graph, SIAM J. Comput. 16 (1987) 358] and hereby obtain a very simple exact algorithm of complexity OË(m4n), being as fast as the first algorithm proposed for this problem [A polynomial time algorithm for minimum cycle basis in directed graphs, Kurt Mehlhorn's List of Publications, 185, MPI, Saarbrücken, 2004, http://www.mpi-sb.mpg.de/~mehlhorn/ftp/DirCycleBasis.ps; Proc. STACS 2005, submitted for publication]. Moreover, the speed-up of Golynski and Horton [A polynomial time algorithm to find the minimum cycle basis of a regular matroid, in: M. Penttonen, E. Meineche Schmidt (Eds.), SWAT 2002, Lecture Notes in Comput. Sci., vol. 2368, Springer, Berlin, 2002, pp. 200-209] applies to this problem, providing an exact algorithm of complexity OË(mÏ+1n), in particular OË(m3.376n). Finally, we prove that these greedy approaches fail for more specialized subclasses of directed cycle bases.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 94, Issue 3, 16 May 2005, Pages 107-112
Journal: Information Processing Letters - Volume 94, Issue 3, 16 May 2005, Pages 107-112
نویسندگان
Christian Liebchen, Romeo Rizzi,