PL
 |
EN
Nowa wersja platformy, zawierająca wyłącznie zasoby pełnotekstowe, jest już dostępna.
Przejdź na https://bibliotekanauki.pl
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 11

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last
Wyniki wyszukiwania
Wyszukiwano:
w słowach kluczowych:  spanning tree
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available remote Local Properties of Triangular Graphs
100%
Mazurkiewicz A.
Fundamenta Informaticae
|
2007
|
tom Vol. 79, nr 3-4
487-495
EN
In the paper triangular graphs are discussed. The class of triangular graphs is of special interest as unifying basic features of complete graphs and trees. The main issue addressed in the paper is to characterize class of triangular graphs (defined globally) by local means. Namely, it is proved that any triangular graph can be constructed from a singleton by successive extensions with nodes having complete neighborhoods. Next, the proved theoretical properties are applied for designing some local algorithms for triangular graphs: for elections a leader and for constructing their spanning trees. The fairness of these algorithms is proved, which means that any node can be elected and any spanning tree can be constructed by execution of these algorithms.
2
Content available remote Spanning Trees whose Stems have a Bounded Number of Branch Vertices
100%
Yan Z.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 3
773-778
EN
Let T be a tree, a vertex of degree one and a vertex of degree at least three is called a leaf and a branch vertex, respectively. The set of leaves of T is denoted by Leaf(T). The subtree T − Leaf(T) of T is called the stem of T and denoted by Stem(T). In this paper, we give two sufficient conditions for a connected graph to have a spanning tree whose stem has a bounded number of branch vertices, and these conditions are best possible.
3
Content available remote On a Spanning k-Tree in which Specified Vertices Have Degree Less Than k
100%
Matsumura H.
Discussiones Mathematicae Graph Theory
|
2015
|
tom 35
|
nr 1
191-196
EN
A k-tree is a tree with maximum degree at most k. In this paper, we give a degree sum condition for a graph to have a spanning k-tree in which specified vertices have degree less than k. We denote by σk(G) the minimum value of the degree sum of k independent vertices in a graph G. Let k ≥ 3 and s ≥ 0 be integers, and suppose G is a connected graph and σk(G) ≥ |V (G)|+s−1. Then for any s specified vertices, G contains a spanning k-tree in which every specified vertex has degree less than k. The degree condition is sharp.
4
Content available remote Efficient Parallel Query Processing by Graph Ranking
100%
Dereniowski D. , Kubale M.
Fundamenta Informaticae
|
2006
|
tom Vol. 69, nr 3
273-285
EN
In this paper we deal with the problem of finding an optimal query execution plan in database systems. We improve the analysis of a polynomial-time approximation algorithm due to Makino et al. for designing query execution plans with almost optimal number of parallel steps. This algorithm is based on the concept of edge ranking of graphs. We use a new upper bound for the edge ranking number of a tree to derive a better worst-case performance guarantee for this algorithm. We also present some experimental results obtained during the tests of the algorithm on random graphs in order to compare the quality of both approximation ratios on average. Both theoretical analysis and experimental results indicate the superiority of our approach.
5
Content available Minimum vertex ranking spanning tree problem for chordal and proper interval graphs
100%
Dereniowski D.
Discussiones Mathematicae Graph Theory
|
2009
|
tom 29
|
nr 2
253-261
EN
A vertex k-ranking of a simple graph is a coloring of its vertices with k colors in such a way that each path connecting two vertices of the same color contains a vertex with a bigger color. Consider the minimum vertex ranking spanning tree (MVRST) problem where the goal is to find a spanning tree of a given graph G which has a vertex ranking using the minimal number of colors over vertex rankings of all spanning trees of G. K. Miyata et al. proved in [NP-hardness proof and an approximation algorithm for the minimum vertex ranking spanning tree problem, Discrete Appl. Math. 154 (2006) 2402-2410] that the decision problem: given a simple graph G, decide whether there exists a spanning tree T of G such that T has a vertex 4-ranking, is NP-complete. In this paper we improve this result by proving NP-hardness of finding for a given chordal graph its spanning tree having vertex 3-ranking. This bound is the best possible. On the other hand we prove that MVRST problem can be solved in linear time for proper interval graphs.
6
Content available Closure for spanning trees and distant area
100%
Fujisawa J. , Saito A. , Schiermeyer I.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 1
143-159
EN
A k-ended tree is a tree with at most k endvertices. Broersma and Tuinstra [3] have proved that for k ≥ 2 and for a pair of nonadjacent vertices u, v in a graph G of order n with $deg_G u + deg_G v ≥ n-1$, G has a spanning k-ended tree if and only if G+uv has a spanning k-ended tree. The distant area for u and v is the subgraph induced by the set of vertices that are not adjacent with u or v. We investigate the relationship between the condition on $deg_G u + deg_G v$ and the structure of the distant area for u and v. We prove that if the distant area contains $K_r$, we can relax the lower bound of $deg_G u + deg_G v$ from n-1 to n-r. And if the distant area itself is a complete graph and G is 2-connected, we can entirely remove the degree sum condition.
7
Content available remote Efficient Implementation of the Italiano Algorithms for Updating the Transitive Closure on Associative Parallel Processors
63%
Nepomniaschay A.
Fundamenta Informaticae
|
2008
|
tom Vol. 89, nr 2-3
313-329
EN
We propose a simple data structure for an efficient implementation of the Italiano algorithms for the dynamic updating of the transitive closure of a directed graph represented as adjacency matrix on a model of associative (or content addressable) parallel processors with vertical processing (the STAR–machine). Associative versions of the Italiano algorithms are represented as procedures DeleteArc1 and InsertArc1. We prove the correctness of these procedures and evaluate their time and space complexity. We also present the main advantages of associative versions of the Italiano algorithms.
8
Content available Algorytm poszukiwania z zabronieniami dla problemu centralnego drzewa rozpinającego
63%
Makuchowski M.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2011
|
tom T. 15, z. 2
319-326
PL
W pracy analizuje się problem znajdowania centralnego drzewa rozpinającego. Problem ten polega na znalezieniu takiego drzewa rozpinającego graf, aby największa odległość od wszystkich pozostałych drzew była możliwie najmniejsza. Odległość pomiędzy drzewami jest miarą zliczającą różnice w zbiorze krawędzi porównywanych drzew. Zagadnienie to należy do klasy problemów NP-trudnych. W pracy proponuje się algorytm, oparty na metodzie poszukiwania z zabronieniami, dedykowany rozpatrywanemu problemowi. Praca zawiera także wyniki eksperymentów numerycznych testujących efektywność proponowanego algorytmu oraz porównuje go z algorytmem dokładnym opartym na metodzie podziału i ograniczeń.
EN
In this paper the central spanning tree problem is considered. The problem consists in finding a spanning tree in a graph, that minimizes the maximum distance to all other spanning trees. The distance between two trees is measured by means of the symmetric difference of their edge sets. The problem is known to be NP-hard. The algorithm based on the tabu search approach is proposed. Computational experiments are conducted and compared with results obtained by a branch and bound algorithm.
9
Sieci sensoryczne w układach monitorowania zagrożeń środowiskowych
63%
Miedziński B. , Staniec K. , Rutecki K. , Debita G. , Majewski J.
Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne
|
2010
|
tom nr 8-9
778-786
PL
Przedstawiono kierunki prac badawczych dotyczących projektowania sieci sensorycznej, w układach monitorowania zagrożeń środowiskowych. Na podstawie uzyskanych wyników i badań omówiono problemy związane z projektowaniem topologii i organizacji sieci WSN tak dla segmentu lokalnego (sensorycznego), na bazie sieci IEEE 802.15.4, jak i dla transportowego. W segmencie lokalnym przeanalizowano algorytmy rozpinania sieci pod kątem elastyczności, w zakresie dowolnego programowania oraz wewnątrzsystemowej kompatybilności elektromagnetycznej. Analizując segment transportowy sieci WSN przy użyciu programowalnych terminali GSM - przedyskutowano wyniki dotyczące efektywności kosztowej proponowanego rozwiązania.
EN
The paper presents obtained results and research domains of studies on a wire-less sensor network for monitoring environmental threats. Analyzed is the issue of designing the topology and network organization in WSN for the local (sensor) segment based on 802.15.4 as well as for the transport segment. In the local segment, network spanning algorithms have been analyzed with respect to the flexibility in free programming and the intra-system electromagnetic compatibility. The transport segment analysis of the WSN network included the use of programmable GSM terminals - outcomes on the cost efficiency of the proposed solution have been presented. The study on the GSM technology is summarized with the presentation of the pre-pilot version of the designed network.
10
Content available Spanning trees with many or few colors in edge-colored graphs
63%
Broersma H. , Li X.
Discussiones Mathematicae Graph Theory
|
1997
|
tom 17
|
nr 2
259-269
EN
Given a graph G = (V,E) and a (not necessarily proper) edge-coloring of G, we consider the complexity of finding a spanning tree of G with as many different colors as possible, and of finding one with as few different colors as possible. We show that the first problem is equivalent to finding a common independent set of maximum cardinality in two matroids, implying that there is a polynomial algorithm. We use the minimum dominating set problem to show that the second problem is NP-hard.
11
Content available An analysis of the applicatiblity of "Hot-Potato" routing in wireless sensor networks used in energy consumption monitoring systems
51%
Dubalski B. , Kiedrowski P. , Pedersen J. M.
Zeszyty Naukowe. Elektrotechnika / Uniwersytet Technologiczno-Przyrodniczy w Bydgoszczy
|
2010
|
tom z. 15
5-24
EN
The subject of this paper is analysis of possibility of application "Hot-Potato" protocol in the Wireless Sensor Networks (WSN), which can be used to collect, store and process data obtained from the media consumption meters. Authors propose to use this protocol on account of its low energy emission and small memory capacity while ensuring the high reliability. To perform this analysis the elements of graph theory were used.
PL
Przedmiotem niniejszego artykułu jest analiza możliwości zastosowania protokołu "Hot-Potato" w bezprzewodowych sieciach sensorowych (WSN), których zadaniem jest zbieranie, przechowywanie i obróbka danych otrzymywanych z liczników monitorujących zużycie mediów. Autorzy proponują zastosowanie tego protokołu ze względu na niską jego emisyjność i niewielką pojemność zastosowanych pamięci przy równoczesnym zachowaniu odpowiedniej niezawodności. W celu dokonania tej analizy wykorzystano elementy teorii grafów.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.