Minimum Linear Arrangement of Series-Parallel Graphs

C. Scheideler, M. Eikel, A. Setzer, in:, Proceedings of the 12th Workshop on Approximation and Online Algorithms (WAOA), 2014, pp. 168–180.

Download
Restricted 397-WAOA14_01.pdf 365.82 KB
Conference Paper
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.
Publishing Year
Proceedings Title
Proceedings of the 12th Workshop on Approximation and Online Algorithms (WAOA)
Page
168--180
LibreCat-ID

Cite this

Scheideler C, Eikel M, Setzer A. Minimum Linear Arrangement of Series-Parallel Graphs. In: Proceedings of the 12th Workshop on Approximation and Online Algorithms (WAOA). LNCS.; 2014:168-180.
Scheideler, C., Eikel, M., & Setzer, A. (2014). Minimum Linear Arrangement of Series-Parallel Graphs. In Proceedings of the 12th Workshop on Approximation and Online Algorithms (WAOA) (pp. 168–180).
@inbook{Scheideler_Eikel_Setzer_2014, series={LNCS}, title={Minimum Linear Arrangement of Series-Parallel Graphs}, booktitle={Proceedings of the 12th Workshop on Approximation and Online Algorithms (WAOA)}, author={Scheideler, Christian and Eikel, Martina and Setzer, Alexander}, year={2014}, pages={168–180}, collection={LNCS}}
Scheideler, Christian, Martina Eikel, and Alexander Setzer. “Minimum Linear Arrangement of Series-Parallel Graphs.” In Proceedings of the 12th Workshop on Approximation and Online Algorithms (WAOA), 168–80. LNCS, 2014.
C. Scheideler, M. Eikel, and A. Setzer, “Minimum Linear Arrangement of Series-Parallel Graphs,” in Proceedings of the 12th Workshop on Approximation and Online Algorithms (WAOA), 2014, pp. 168–180.
Scheideler, Christian, Martina Eikel, and Alexander Setzer. “Minimum Linear Arrangement of Series-Parallel Graphs.” Proceedings of the 12th Workshop on Approximation and Online Algorithms (WAOA). N.p., 2014. 168–180. Print. LNCS.
Main File(s)
File Name
397-WAOA14_01.pdf 365.82 KB
Access Level
Restricted Closed Access
Last Uploaded
2018-03-20T06:58:44Z


Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar