Minimum Linear Arrangement of Series-Parallel Graphs

DOI10.1007/978-3-319-18263-6_15MaRDI QIDQ3453293zbMATH OpenOpenAlexFDO

Authors Martina Eikel, Alexander Setzer, Christian Scheideler

Publication date 20 November 2015

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

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

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)

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}^{\ast }|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.

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; zbMATH DE number 6387522
• scientific article; zbMATH DE number 1560506
• Minimum linear arrangements
• A New Lower Bound for the Minimum Linear Arrangement of a Graph

Cites work

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

Cited in

(16)

• Linear arrangement problems on recursively partitioned graphs
• scientific article; zbMATH DE number 6254006 (Why is no real title available?)
• On an ordering problem in weighted hypergraphs
• Ordering a Sparse Graph to Minimize the Sum of Right Ends of Edges
• Scheduling series-parallel task graphs to minimize peak memory
• A divide and conquer algorithm for \(d\)-dimensional arrangement
• Computing an optimal orientation of a balanced decomposition tree for linear arrangement problems
• scientific article; zbMATH DE number 7378361 (Why is no real title available?)
• Minimum linear arrangement of chord graphs
• scientific article; zbMATH DE number 1560506 (Why is no real title available?)
• Minimum Cell Connection in Line Segment Arrangements
• A note on minimum linear arrangement for BC graphs
• Minimum linear arrangement of the Cartesian product of optimal order graph and path
• Tractable parameterizations for the minimum linear arrangement problem
• Tractable parameterizations for the minimum linear arrangement problem
• Planar linear arrangements of outerplanar 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)