Informacja

Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

Wyszukujesz frazę "(long, optimal, Hamilton) cycle" wg kryterium: Temat


Wyświetlanie 1-1 z 1
Tytuł:
Heavy cycles in weighted graphs
Autorzy:
Bondy, J.
Broersma, Hajo
van den Heuvel, Jan
Veldman, Henk
Powiązania:
https://bibliotekanauki.pl/articles/743527.pdf
Data publikacji:
2002
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
weighted graph
(long, optimal, Hamilton) cycle
(edge-, vertex-)weighting
weighted degree
Opis:
An (edge-)weighted graph is a graph in which each edge e is assigned a nonnegative real number w(e), called the weight of e. The weight of a cycle is the sum of the weights of its edges, and an optimal cycle is one of maximum weight. The weighted degree w(v) of a vertex v is the sum of the weights of the edges incident with v. The following weighted analogue (and generalization) of a well-known result by Dirac for unweighted graphs is due to Bondy and Fan. Let G be a 2-connected weighted graph such that w(v) ≥ r for every vertex v of G. Then either G contains a cycle of weight at least 2r or every optimal cycle of G is a Hamilton cycle. We prove the following weighted analogue of a generalization of Dirac's result that was first proved by Pósa. Let G be a 2-connected weighted graph such that w(u)+w(v) ≥ s for every pair of nonadjacent vertices u and v. Then G contains either a cycle of weight at least s or a Hamilton cycle. Examples show that the second conclusion cannot be replaced by the stronger second conclusion from the result of Bondy and Fan. However, we characterize a natural class of edge-weightings for which these two conclusions are equivalent, and show that such edge-weightings can be recognized in time linear in the number of edges.
Źródło:
Discussiones Mathematicae Graph Theory; 2002, 22, 1; 7-15
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
    Wyświetlanie 1-1 z 1

    Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies