Publications Repository - Gdańsk University of Technology

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).

Authors

• Piotr Borowiecki,
• prof. dr hab. inż. Dariusz Dereniowski link open in new tab ,
• mgr inż. Dorota Osula link open in new tab