Autor: Lacko, Vladimír - Katalog OPAC zbiorów

Skocz do pozycji: 1.

Tytuł:: Persistency in the Traveling Salesman Problem on Halin graphs
Autorzy:: Lacko, Vladimír
Powiązania:: https://bibliotekanauki.pl/articles/743793.pdf
Data publikacji:: 2000
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: persistency
traveling salesman problem
Halin graph
polynomial algorithm
Opis:: For the Traveling Salesman Problem (TSP) on Halin graphs with three types of cost functions: sum, bottleneck and balanced and with arbitrary real edge costs we compute in polynomial time the persistency partition $E_{All}$, $E_{Some}$, $E_{None}$ of the edge set E, where:
$E_{All}$ = {e ∈ E, e belongs to all optimum solutions},
$E_{None}$ = {e ∈ E, e does not belong to any optimum solution} and
$E_{Some}$ = {e ∈ E, e belongs to some but not to all optimum solutions}.
Źródło:: Discussiones Mathematicae Graph Theory; 2000, 20, 2; 231-242
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 2.

Tytuł:: Balanced problems on graphs with categorization of edges
Autorzy:: Berežný, Štefan
Lacko, Vladimír
Powiązania:: https://bibliotekanauki.pl/articles/743374.pdf
Data publikacji:: 2003
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: algorithms on graphs
categorization of edges
NP-completeness
Opis:: Suppose a graph G = (V,E) with edge weights w(e) and edges partitioned into disjoint categories S₁,...,Sₚ is given. We consider optimization problems on G defined by a family of feasible sets (G) and the following objective function:
$L₅(D) = max_{1≤i≤p} (max_{e ∈ S_i ∩ D} w(e) - min_{e ∈ S_i ∩ D} w(e))$
For an arbitrary number of categories we show that the L₅-perfect matching, L₅-a-b path, L₅-spanning tree problems and L₅-Hamilton cycle (on a Halin graph) problem are NP-complete.
We also summarize polynomiality results concerning above objective functions for arbitrary and for fixed number of categories.
Źródło:: Discussiones Mathematicae Graph Theory; 2003, 23, 1; 5-21
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Informacja