Wszystkie pola: Shang, Shang - Katalog OPAC zbiorów

Skocz do pozycji: 1.

Tytuł:: A simple linear algorithm for the connected domination problem in circular-arc graphs
Autorzy:: Hung, Ruo-Wei
Chang, Maw-Shang
Powiązania:: https://bibliotekanauki.pl/articles/744451.pdf
Data publikacji:: 2004
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: graph algorithms
circular-arc graphs
connected dominating set
shortest path
Opis:: A connected dominating set of a graph G = (V,E) is a subset of vertices CD ⊆ V such that every vertex not in CD is adjacent to at least one vertex in CD, and the subgraph induced by CD is connected. We show that, given an arc family F with endpoints sorted, a minimum-cardinality connected dominating set of the circular-arc graph constructed from F can be computed in O(|F|) time.
Źródło:: Discussiones Mathematicae Graph Theory; 2004, 24, 1; 137-145
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 2.

Tytuł:: Branch-Weight Unique Trees
Autorzy:: Shang, Jen-Ling
Powiązania:: https://bibliotekanauki.pl/articles/32361727.pdf
Data publikacji:: 2022-05-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: branch-weight
branch-weight sequence
branch-weight unique
tree
spider
Opis:: A branch at a vertex x in a tree is a maximal subtree containing x as an endvertex. The branch-weight of x is the maximum number of edges in any branch at x. The branch-weight sequence of a tree is the multiset consisting of the branch-weights of all vertices arranged in nonincreasing order. Non-isomorphic trees may have the same branch-weight sequence. A tree T is said to be branch-weight unique in a family of trees if T is uniquely determined in the family by its branch-weight sequence. A spider is a tree in which exactly one vertex has degree exceeding two. It is known that spiders are branch-weight unique in the family of spiders but not in the family of all trees. In this study, a necessary and sufficient condition is obtained whereby a spider may be branch-weight unique in the family of all trees. Moreover, two types of trees are proposed to be branch-weight unique in the family of all trees.
Źródło:: Discussiones Mathematicae Graph Theory; 2022, 42, 2; 405-416
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Informacja