Wyszukiwarka
Abstrakt
The tree-depth problem can be seen as finding an elimination tree of minimum height for a given input graph G. We introduce a bicriteria generalization in which additionally the width of the elimination tree needs to be bounded by some input integer b. We are interested in the case when G is the line graph of a tree, proving that the problem is NP-hard and obtaining a polynomial-time additive 2b-approximation algorithm. This particular class of graphs received significant attention in the past, mainly due to a number of potential applications, e.g.in parallel assembly of modular products, or parallel query processing in relational databases, as well as purely combinatorial applications including searching in tree-like partial orders (which in turn generalizes binary search on sorted data).
Cytowania
-
0
CrossRef
-
0
Web of Science
-
0
Scopus
Autorzy (3)
-
Piotr Borowiecki
- University of Zielona Góra
-
Cytuj jako
Pełna treść
pełna treść publikacji nie jest dostępna w portalu
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuły w czasopismach
- Opublikowano w:
-
THEORETICAL COMPUTER SCIENCE
nr 947,
ISSN: 0304-3975 - Język:
- angielski
- Rok wydania:
- 2023
- Opis bibliograficzny:
- Borowiecki P., Dereniowski D., Osula D.: The complexity of bicriteria tree-depth// THEORETICAL COMPUTER SCIENCE -Vol. 947, (2023), s.113682-
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.tcs.2022.12.032
- Źródła finansowania:
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 83 razy
Publikacje, które mogą cię zainteresować
Exploiting multi-interface networks: Connectivity and Cheapest Paths
- A. Kosowski,
- A. Navarra,
- C. Pinotti
On extremal sizes of locally k-tree graphs
- M. Borowiecki,
- P. Borowiecki,
- E. Sidorowicz
- + 1 autorów