Temat: graphs theory - Katalog OPAC zbiorów

Skocz do pozycji: 1.

Tytuł:: Algorytmy heurystyczne dla problemu minimalizacji sumy kosztów zadań opóźnionych
Heuristics algorithms for the single machine total tardiness problem.
Autorzy:: Wodecki, Mieczysław
Powiązania:: https://bibliotekanauki.pl/articles/748154.pdf
Data publikacji:: 1999
Wydawca:: Polskie Towarzystwo Matematyczne
Tematy:: Scheduling theory, deterministic
Programming involving graphs or networks
Opis:: W pracy rozpatrujemy problem minimalizacji sumy kosztów opóźnień zadań wykonywanych na jednej maszynie. Należy on do klasy problemów silnie NP-zupełnych. Zamieszczone w literaturze wyniki obliczeniowe wskazują, że w rozsądnym czasie można uzyskać jego rozwiązanie optymalne jedynie dla przykładów o niewielkich rozmiarach. Z tego właśnie powodu proponujemy szybki algorytm heurystyczny oraz algorytm typu „popraw” oparty na metodzie tabu search.
This paper presents approximations algorithms for the single machine total weighted tardiness problems. The algorithms is based on a tabu search technique with a specific neighborhood definition. Results of testing the algorithms on large number of randomly generated examples are also given and analysed.
Źródło:: Mathematica Applicanda; 1999, 27, 41
1730-2668
2299-4009
Pojawia się w:: Mathematica Applicanda
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 2.

Tytuł:: Analysis of the efficiency of graph coloring algorithms
Autorzy:: Kubale, Marek
Powiązania:: https://bibliotekanauki.pl/articles/748571.pdf
Data publikacji:: 1982
Wydawca:: Polskie Towarzystwo Matematyczne
Tematy:: Computational complexity and efficiency of algorithms
Coloring of graphs and hypergraphs
Graph theory
Opis:: .
This paper discusses the computational efficiency and the number of colors used by the following algorithms for coloring vertices of graphs: sequential coloring and sequential coloring with interchange algorithms for a largest-first and a smallest-last orderings of vertices, the coloring-pairs algorithm, and the approximately maximum independent set algorithm. Each algorithm is supplied with a Pascal-like program, time complexity in terms of the size of a graph, and worst-case behaviour. In conclusion, some computational results are included with support the estimations and suggest the sequential coloring with interchange algorithm for a largest-first vertex ordering as a method which uses the least number of colors for uniformly distributed random graphs.
Źródło:: Mathematica Applicanda; 1982, 10, 19
1730-2668
2299-4009
Pojawia się w:: Mathematica Applicanda
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 3.

Tytuł:: An algorithm for the solution of the traveling salesman problem via disjunctive graphs
Autorzy:: Grabowski, Józef
Powiązania:: https://bibliotekanauki.pl/articles/748529.pdf
Data publikacji:: 1978
Wydawca:: Polskie Towarzystwo Matematyczne
Tematy:: Directed graphs (digraphs), tournaments
Scheduling theory, deterministic
Special problems of linear programming(transportation, multi-index, etc.)
Opis:: .
From the introduction: "The traveling salesman problem is a problem of combinatorial type. Although problems of this type sometimes have a relatively simple formulation, there are many difficulties associated with their solution even when the most up-to-date computers are used. In the 1970s many papers have been devoted to this problem. The purpose of the vast majority of them has been to find more effective solution algorithms. "In this paper we give the solution of the traveling salesman problem via disjunctive graphs. Up to now the elements of disjunctive graphs have been used to solve problems connected with the determination of an optimal task completion sequence.''
Źródło:: Mathematica Applicanda; 1978, 6, 13
1730-2668
2299-4009
Pojawia się w:: Mathematica Applicanda
Dostawca treści:: Biblioteka Nauki

Artykuł

Informacja