Minimum Linear Arrangement of Series-Parallel Graphs

DOI10.1007/978-3-319-18263-6_15zbMATH Open1457.68212arXiv1410.4395OpenAlexW13423557MaRDI QIDQ3453293FDOQ3453293

Christian Scheideler, Martina Eikel, Alexander Setzer

Publication date: 20 November 2015

Published in: Approximation and Online Algorithms (Search for Journal in Brave)

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|lo{g}^{*}|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.

Full work available at URL: https://arxiv.org/abs/1410.4395

Recommendations

• Minimum-maximal matching in series-parallel graphs
• Minimum linear arrangement of chord graphs
• On Mixed Linear Layouts of Series-Parallel Graphs
• On mixed linear layouts of series-parallel graphs
• Lower bounds for the minimum linear arrangement of a graph
• scientific article
• scientific article; zbMATH DE number 1560506
• Minimum linear arrangements
• A New Lower Bound for the Minimum Linear Arrangement of a Graph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Approximation algorithms (68W25)

Cites Work

• Optimal Assignments of Numbers to Vertices
• Expander flows, geometric embeddings and graph partitioning
• Some simplified NP-complete graph problems
• On bipartite drawings and the linear arrangement problem
• Optimal Linear Ordering
• Experiments on the minimum linear arrangement problem
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• Parallel recognition of series-parallel graphs
• Single Machine Job Sequencing with Precedence Constraints
• An improved approximation ratio for the minimum linear arrangement problem
• Linear-time computability of combinatorial problems on series-parallel graphs
• Minimum linear arrangement of chord graphs
• Planar linear arrangements of outerplanar graphs
• Optimal Linear Arrangement of Interval Graphs
• Parallel algorithms for series parallel graphs
• A linear algorithm for the domination number of a series-parallel graph
• Optimal linear arrangement of a rectangular grid

Cited In (12)

• Minimum Linear Arrangement of the Cartesian Product of Optimal Order Graph and Path
• On an ordering problem in weighted hypergraphs
• Minimum linear arrangement of chord graphs
• A note on minimum linear arrangement for BC graphs
• Title not available (Why is that?)
• Computing an optimal orientation of a balanced decomposition tree for linear arrangement problems
• Title not available (Why is that?)
• Minimum Cell Connection in Line Segment Arrangements
• Ordering a Sparse Graph to Minimize the Sum of Right Ends of Edges
• Planar linear arrangements of outerplanar graphs
• Title not available (Why is that?)
• Linear arrangement problems on recursively partitioned graphs

This page was built for publication: Minimum Linear Arrangement of Series-Parallel Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3453293)