Generation of weighted trees, block trees and block graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914645187493888 |
|---|---|
| author | Ekim, Tınaz Shalom, Mordechai Yirik, Mehmet Aziz |
| author_facet | Ekim, Tınaz Shalom, Mordechai Yirik, Mehmet Aziz |
| contents | We present a general framework to generate trees every vertex of which has a non-negative weight and a color. The colors are used to impose certain restrictions on the weight and colors of other vertices. We first extend the enumeration algorithms of unweighted trees given in [19, 20] to generate weighted trees that allow zero weight. We avoid isomorphisms by generalizing the concept of centroids to weighted trees and then using the so-called centroid-rooted canonical weighted trees. We provide a time complexity analysis of unranking algorithms and also show that the output delay complexity of enumeration is linear. The framework can be used to generate graph classes taking advantage of their tree-based decompositions/representations. We demonstrate our framework by generating weighted block trees which are in one-to-one correspondence with connected block graphs. All connected block graphs up to 19 vertices are publicly available at [1]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_09764 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Generation of weighted trees, block trees and block graphs Ekim, Tınaz Shalom, Mordechai Yirik, Mehmet Aziz Discrete Mathematics Data Structures and Algorithms We present a general framework to generate trees every vertex of which has a non-negative weight and a color. The colors are used to impose certain restrictions on the weight and colors of other vertices. We first extend the enumeration algorithms of unweighted trees given in [19, 20] to generate weighted trees that allow zero weight. We avoid isomorphisms by generalizing the concept of centroids to weighted trees and then using the so-called centroid-rooted canonical weighted trees. We provide a time complexity analysis of unranking algorithms and also show that the output delay complexity of enumeration is linear. The framework can be used to generate graph classes taking advantage of their tree-based decompositions/representations. We demonstrate our framework by generating weighted block trees which are in one-to-one correspondence with connected block graphs. All connected block graphs up to 19 vertices are publicly available at [1]. |
| title | Generation of weighted trees, block trees and block graphs |
| topic | Discrete Mathematics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2401.09764 |