Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Balanced problems on graphs with categorization of edges

100%

Berežný Š., Lacko V.

Discussiones Mathematicae Graph Theory

2003

tom 23

nr 1

5-21

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.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Berežný Š.

1 Lacko V.

1 2003

Wyniki wyszukiwania

Balanced problems on graphs with categorization of edges