Temat: BRANCH - Katalog OPAC zbiorów

Skocz do pozycji: 1.

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ł

Skocz do pozycji: 2.

Tytuł:: Spanning Trees whose Stems have a Bounded Number of Branch Vertices
Autorzy:: Yan, Zheng
Powiązania:: https://bibliotekanauki.pl/articles/31340783.pdf
Data publikacji:: 2016-08-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: spanning tree
stem
branch vertex
Opis:: 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.
Źródło:: Discussiones Mathematicae Graph Theory; 2016, 36, 3; 773-778
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 3.

Tytuł:: When is an Incomplete 3 × n Latin Rectangle Completable?
Autorzy:: Euler, Reinhardt
Oleksik, Paweł
Powiązania:: https://bibliotekanauki.pl/articles/30146857.pdf
Data publikacji:: 2013-03-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: incomplete latin rectangle
completability
solution space enumeration
branch-and-bound
Opis:: We use the concept of an availability matrix, introduced in Euler [7], to describe the family of all minimal incomplete 3 × n latin rectangles that are not completable. We also present a complete description of minimal incomplete such latin squares of order 4.
Źródło:: Discussiones Mathematicae Graph Theory; 2013, 33, 1; 57-69
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 4.

Tytuł:: An Efficient Polynomial Time Approximation Scheme for the Vertex Cover P₃ Problem on Planar Graphs
Autorzy:: Tu, Jianhua
Shi, Yongtang
Powiązania:: https://bibliotekanauki.pl/articles/31343724.pdf
Data publikacji:: 2019-02-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: combinatorial optimization
vertex cover P3 problem
branch- width
planar graphs
EPTAS
Opis:: Given a graph G = (V,E), the task in the vertex cover P₃(VCP₃) problem is to find a minimum subset of vertices F ⊆ V such that every path of order 3 in G contains at least one vertex from F. The VCP₃ problem remains NP-hard even in planar graphs and has many applications in real world. In this paper, we give a dynamic-programming algorithm to solve the VCP₃ problem on graphs of bounded branchwidth. Using the dynamic programming algorithm and the Baker’s EPTAS framework for NP-hard problems, we present an efficient polynomial time approximation scheme (EPTAS) for the VCP₃ problem on planar graphs.
Źródło:: Discussiones Mathematicae Graph Theory; 2019, 39, 1; 55-65
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Informacja