Search
Abstract
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).
Citations
-
0
CrossRef
-
0
Web of Science
-
0
Scopus
Authors (3)
-
Piotr Borowiecki
- University of Zielona Góra
-
Cite as
Full text
full text is not available in portal
Keywords
Details
- Category:
- Articles
- Type:
- artykuły w czasopismach
- Published in:
-
THEORETICAL COMPUTER SCIENCE
no. 947,
ISSN: 0304-3975 - Language:
- English
- Publication year:
- 2023
- Bibliographic description:
- Borowiecki P., Dereniowski D., Osula D.: The complexity of bicriteria tree-depth// THEORETICAL COMPUTER SCIENCE -Vol. 947, (2023), s.113682-
- DOI:
- Digital Object Identifier (open in new tab) 10.1016/j.tcs.2022.12.032
- Sources of funding:
- Verified by:
- Gdańsk University of Technology
seen 40 times
Recommended for you
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 authors