Minimum Linear Arrangement of Series-Parallel Graphs

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

Authors: Martina Eikel, Alexander Setzer, Christian Scheideler 

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

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; 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

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 (16)

• On an ordering problem in weighted hypergraphs
• Minimum linear arrangement of chord graphs
• A note on minimum linear arrangement for BC graphs
• Minimum linear arrangement of the Cartesian product of optimal order graph and path
• 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?)
• A divide and conquer algorithm for \(d\)-dimensional arrangement
• 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
• Scheduling series-parallel task graphs to minimize peak memory
• Tractable parameterizations for the minimum linear arrangement problem
• Tractable parameterizations for the minimum linear arrangement problem
• 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)