Minimum Linear Arrangement of Series-Parallel Graphs
From MaRDI portal
Publication:3453293
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
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
