---
res:
bibo_abstract:
- 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.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Christian
foaf_name: Scheideler, Christian
foaf_surname: Scheideler
foaf_workInfoHomepage: http://www.librecat.org/personId=20792
- foaf_Person:
foaf_givenName: Martina
foaf_name: Eikel, Martina
foaf_surname: Eikel
- foaf_Person:
foaf_givenName: Alexander
foaf_name: Setzer, Alexander
foaf_surname: Setzer
foaf_workInfoHomepage: http://www.librecat.org/personId=11108
dct_date: 2014^xs_gYear
dct_title: Minimum Linear Arrangement of Series-Parallel Graphs@
...