Analiza przybliżonego algorytmu dla problemu szukania drzewa spinającego o minimalnym uporządkowanym indeksie chromatycznym

• Autorzy: Dereniowski D.

Warianty tytułu

EN

Analysis of an approximate algorithm for the minimum edge ranking spanning tree problem

• Języki publikacji: PL

Abstrakty

PL

Uporządkowane kolorowanie krawędzi grafu polega na takim etykietowaniu krawędzi liczbami naturalnymi, że każda ścieżka łącząca krawędzie o jednakowej barwie zawiera krawędź o kolorze wyższym. W pracy rozważamy problem kombinatoryczny MERST, polegający na znalezieniu, dla danego grafu G, jego drzewa spinającego, którego uporządkowany indeks chromatyczny jest najmniejszy. spośród indeksów chromatycznych wszystkich drzew spinających. Makino, Uno i Ibaraki [1] podali przybliżony algorytm rozwiązujący powyższy problem w przypadku grafów ogólnych. W pracy podajemy lepszą funkcję dobroci od tej, która została podana w [1] oraz prezentujemy wyniki testów komputerowych zebranych podczas implementacji algorytmu. Testy obejmują zarówno porównanie funkcji dobroci, jak i oszacowań uporządkowanego indeksu chromatycznego drzew, na podstawie których uzyskano opisane funkcje dobroci.

EN

Edge k-ranking of a graph is a labeling of its edges with k colors such that each path between two edges having the same color contains an edge with a bigger color. The edge ranking number of a graph G is denoted by xr'(G) and defined as the smallest integer k such that there exists an edge k-ranking of G. In the minimum edge ranking spanning tree problem (MERST) we want to find a spanning tree T of a given graph G such that the value of xr'(T) is as small as possible. There exists a linear time algorithm for the edge ranking problem of trees [6]. However, problem MERST is NP-hard for general graphs [1]. Makino, Uno and Ibaraki gave a polynomial time approximate algorithm solving this problem. In this paper we use the bound proved in [2] to obtain a performance ratio of the algorithm, which is better than the ratio given in [1] for [delta]* > 3.

• Wydawca: Wydział Elektroniki, Telekomunikacji i Informatyki Politechniki Gdańskiej
• Czasopismo: Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne
• Rocznik: 2004
• Tom: T. 5
• Strony: 725--731
• Opis fizyczny: Bibliogr. 8 poz., 1 rys.

Twórcy

autor

Dereniowski D.

• Katedra Algorytmów i Modelowania Systemów, Politechnika Gdańska

• Katedra Algorytmów i Modelowania Systemów, Politechnika Gdańska

Bibliografia

• [1] Makino K., Uno Y., Ibaraki T.: On minimum edge ranking spanning trees, J. Algorithms 38 (2001)411-437.
• [2] Dereniowski D.: Uporządkowane kolorowanie krawędzi grafów dwudzielnych. Raport Techniczny 31/2002 WETIPG, 2002.
• [3] Iyer A.V., Ratliff H.D., Wijayan G.: Parallel assembly of modular products - an analysis, Tech. Report 88-06, Georgia Institute of Technology, 1988.
• [4] Iyer A.V., Ratliff H.D., Wijayan G.: On an edge ranking problem of trees and graphs, Discrete Appl. Math. 30(1991)43-52.
• [5] De la Torre P., Greenlaw R., Schiiffer A.A.: Optimal edge ranking of trees in polynomial time, Algorithmica 13 (1995) 529-618.
• [6] LamT.W., Yue F.L.: Optimal edge ranking of trees in linear time, Proc. of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (1998) 436-445.
• [7] Makino K., Uno Y., Ibaraki T.: Minimum edge ranking spanning trees of threshold graphs, LNCS 2518 (2002) 428-440.
• [8] Furer M., Raghavachari B.: Approximating the minimum-degree Steiner tree to within one of optimal, J. Algorithms 17 (1994) 409-423.