Minimum Linear Arrangement of Series-Parallel Graphs

DOI10.1007/978-3-319-18263-6_15zbMath1457.68212arXiv1410.4395OpenAlexW13423557MaRDI QIDQ3453293

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) Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25)

Related Items

Ordering a Sparse Graph to Minimize the Sum of Right Ends of Edges, Minimum Linear Arrangement of the Cartesian Product of Optimal Order Graph and Path, On an ordering problem in weighted hypergraphs

Cites Work

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