- 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ł