Generowanie sąsiedztwa w algorytmach lokalnych poszukiwań uporządkowanego kolorowania grafów

• Autorzy: Dereniowski, D.

Warianty tytułu

EN

Neighborhood generation in local search algorithms for vertex ranking of graphs

• Konferencja: XV Krajowa Konferencja Automatyzacji Procesów Dyskretnych, Zakopane, 20-23 września 2006r.
• Języki publikacji: PL

Abstrakty

PL

Przedstawienie rozwiązań problemów kombinatorycznych w postaci permutacji daje podstawy do konstrukcji algorytmów lokalnych poszukiwań. Uporządkowane pokolorowanie grafu można zapisać w postaci permutacji wierzchołków grafu. Podstawowe operacje, prowadzące do generowania sąsiedztwa rozwiązania, to zamiana dwóch elementów lub przesunięcie elementu permutacji. W artykule wskazujemy metodę, pozwalającą na wykonanie takich operacji w czasie O(m), przy założeniu, że dane jest drzewo eliminacji wyjściowej permutacji.

EN

Representing solutions to combinatorial problems as permutations allows us to use local search algorithms for solving them. A vertex ranking of a graph can be represented by a permutation of the vertices of the graph. Basic operations for generating a neighborhood of a current solution are swapping two elements of the permutation or changing a position of an element. We show how to perform such operations in time O(m) assuming that an elimination tree of the current permutation is given.

Słowa kluczowe

PL

graf; kolorowanie grafów; kolorowanie uporządkowane; algorytm lokalnych poszukiwań; generowanie sąsiedztwa

EN

graph; graph coloring; ordered coloring; local search algorithm; neighborhood generation

• Czasopismo: Zeszyty Naukowe. Automatyka / Politechnika Śląska
• Rocznik: 2006
• Tom: z. 143
• Strony: 51-56
• Opis fizyczny: Bibliogr. 8 poz.

Twórcy

autor

Dereniowski, D.

• Katedra Algorytmów i Modelowania Systemów Politechniki Gdańskiej, 80-952 Gdańsk Wrzeszcz, ul. Gabriela Narutowicza 11/12, tel.: [phone],

Bibliografia

• 1. Bodlaender H., Deogun J.S., Jansen K., Kloks T., Kratsch D., Muller H., Tuza Z.: Rankings of graphs, SIAM J. Discrete Math. 11, 1998, p. 168-181.
• 2. Bodlaender H., Gilbert R.J., Hafsteinson H., Kloks T.: Approximating treewidth, pathwidth, frontsize, and shortest elimination tree, J. Algorithms 18, 1995, p. 238-255.
• 3. Deogun J.S., Kloks T., Kratsch D., Muller H.: On the vertex ranking problem for trapezoid, circular-arc and other graphs, Discrete Appl. Math. 98, 1999, p. 39-63.
• 4. Dereniowski D., Nadolski A.: Vertex rankings of chordal graphs and weighted trees, Inform. Process. Letters 98, 2006, p. 96-100.
• 5. Liu J.W.H.: Modification of the minimum degree algorithm by multiple elimination, ACM Transactions on Mathematical Software 12, 1985, p. 615-627.
• 6. Liu J.W.H.: The role of elimination trees in sparse factorization, SIAM J. Matrix Analysis and Appl. 11, 1990, p. 134-172.
• 7. Pothen A.: The complexity of optimal elimination trees, Tech. Report CS-88-13, The Pennsylvania State University, 1988.
• 8. Schäffer A.A.: Optimal node ranking of trees in linear time, Inform. Process. Letters 33, 1989/90, p. 91-96.