کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1141509 | 957014 | 2011 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On coloring the arcs of a tournament, covering shortest paths, and reducing the diameter of a graph
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
کنترل و بهینه سازی
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We define closed edge colorings of directed graphs, and state a conjecture about the maximum size of a tournament graph that can be arc-colored with mm colors and contain no closed subgraphs. We prove special cases of this conjecture. We show that if this conjecture is correct then for any (undirected) graph with positive edge lengths and a given subset V′V′ of nodes, covering all the shortest paths between pairs of nodes of V′V′ requires at least |V′|−1|V′|−1 edges. We use the latter property to produce an approximation algorithm with improved bound for minimizing the diameter or the radius of an unweighted graph by adding to it a given number of new edges.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 8, Issue 2, May 2011, Pages 302–314
Journal: Discrete Optimization - Volume 8, Issue 2, May 2011, Pages 302–314
نویسندگان
Nili Guttmann-Beck, Refael Hassin,