Temat: hypergraphs - Katalog OPAC zbiorów

Skocz do pozycji: 1.

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ł

Zmień widok

na półce

Skocz do pozycji: 2.

Tytuł:: The theorems of Koenig and Birkhoff and their connection with the minimization of the duration time of the measurements of automatic telecommunication channels
Autorzy:: Perz, Szczepan
Zaremba, Leszek
Powiązania:: https://bibliotekanauki.pl/articles/748569.pdf
Data publikacji:: 1982
Wydawca:: Polskie Towarzystwo Matematyczne
Tematy:: Channel models (including quantum), Discrete-time control systems, Hypergraphs, Matrix equations and identities, Matrices of integers, Stochastic matrices
Opis:: .
A problem (P) of minimization of the duration time of the measurements of automatic telecommunication channels is considered. P is a discrete optimization problem solved by graph theory methods. It is defined by (i)-(v), where: (i) for each i, 1≤i≤p, and j, 1≤1≤p, there are given k ij channels to be measured between node ”i” and node ”j”; (ii) measurement of one channel lasts one unit; (iii) there are exactly two devices, say A, B, in each node (the case where there is an arbitrary number of devices A, B in each node may be easily reduced to this case); (iv) the channel between node ”i” and node ”j” may be measured only by use of device A being present in node ”i” and device B in node ”j”; (v) in each time both devices A or B may measure only one channel. To solve P, some knowledge of hypergraphs as well as functional analysis (the Krein-Milman theorem) and linear algebra (the Koenig theorem) is necessary. The Koenig theorem is proved in a simple manner similarly as the dual Koenig theorem (which is a new result). As corollaries the Birkhoff theorem about bistochastic matrices and the dual Birkhoff theorem are deduced.
Źródło:: Mathematica Applicanda; 1982, 10, 19
1730-2668
2299-4009
Pojawia się w:: Mathematica Applicanda
Dostawca treści:: Biblioteka Nauki

Artykuł

Zmień widok

na półce

Informacja

Wyszukujesz frazę "hypergraphs" wg kryterium: Temat

Źródło danych

Dostawca treści

Kolekcja

Rok wydania

Wydawca

Temat

Autor

Typ dokumentu

Język