Minimum Linear Arrangement of Series-Parallel Graphs
Scheideler, Christian
Eikel, Martina
Setzer, Alexander
ddc:040
We present a factor $14D^2$ approximation algorithm for the minimum linear arrangement problem on series-parallel graphs, where $D$ is the maximum degree in the graph. Given a suitable decomposition of the graph, our algorithm runs in time $O(|E|)$ and is very easy to implement. Its divide-and-conquer approach allows for an effective parallelization. Note that a suitable decomposition can also be computed in time $O(|E|\log{|E|})$ (or even $O(\log{|E|}\log^*{|E|})$ on an EREW PRAM using $O(|E|)$ processors). For the proof of the approximation ratio, we use a sophisticated charging method that uses techniques similar to amortized analysis in advanced data structures. On general graphs, the minimum linear arrangement problem is known to be NP-hard. To the best of our knowledge, the minimum linear arrangement problem on series-parallel graphs has not been studied before.
2014
info:eu-repo/semantics/conferenceObject
doc-type:conferenceObject
text
http://purl.org/coar/resource_type/c_5794
https://ris.uni-paderborn.de/record/397
Scheideler C, Eikel M, Setzer A. Minimum Linear Arrangement of Series-Parallel Graphs. In: <i>Proceedings of the 12th Workshop on Approximation and Online Algorithms (WAOA)</i>. LNCS. ; 2014:168--180.
info:eu-repo/semantics/closedAccess