Warianty tytułu
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
Abstrakty
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.
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.
Rocznik
Tom
Strony
51-56
Opis fizyczny
Bibliogr. 8 poz.
Twórcy
autor
- Katedra Algorytmów i Modelowania Systemów Politechniki Gdańskiej, 80-952 Gdańsk Wrzeszcz, ul. Gabriela Narutowicza 11/12, tel.: (058) 347-19-56, deren@eti.pg.gda.pl
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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.baztech-article-BSL2-0012-0030