Heuristics for the data arrangement problem on regular trees

Eranda Çela () and Rostislav Staněk ()
Additional contact information
Eranda Çela: TU Graz
Rostislav Staněk: Universität Graz

Journal of Combinatorial Optimization, 2015, vol. 30, issue 3, No 22, 768-802

Abstract: Abstract The data arrangement problem on regular trees (DAPT) consists in assigning the vertices of a given graph G to the leaves of a d-regular tree T such that the sum of the pairwise distances of all pairs of leaves in T which correspond to edges of G is minimised. This problem is a special case of the generic graph embedding problem and is NP-hard for every fixed $$d\ge 2$$ d ≥ 2 . In this paper we propose construction and local search heuristics for the DAPT and introduce a lower bound for this problem. The analysis of the performance of the heuristics is based on two considerations: (a) the quality of the solutions produced by the heuristics as compared to the respective lower bound (b) for a special class of instances with known optimal solution we evaluate the gap between the optimal value of the objective function and the objective function value attained by the heuristic solution, respectively.

Keywords: Combinatorial optimisation; Data arrangement problem; Regular trees; Heuristics; 90C27 (search for similar items in EconPapers)
Date: 2015
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-013-9666-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:30:y:2015:i:3:d:10.1007_s10878-013-9666-0

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-013-9666-0

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().