New Approximation Techniques for Some Linear Ordering Problems
From MaRDI portal
Publication:4651541
DOI10.1137/S0097539702413197zbMath1087.68130MaRDI QIDQ4651541
No author found.
Publication date: 21 February 2005
Published in: SIAM Journal on Computing (Search for Journal in Brave)
approximation algorithmsminimum linear arrangementspreading metricsinterval graph completionstorage-time product
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Approximation algorithms (68W25)
Related Items
Possible and Impossible Attempts to Solve the Treewidth Problem via ILPs ⋮ An improved approximation ratio for the minimum linear arrangement problem ⋮ Convex Relaxations for Permutation Problems ⋮ On a class of metrics related to graph layout problems ⋮ On minimum cost edge searching ⋮ A New Lower Bound for the Minimum Linear Arrangement of a Graph ⋮ Revised GRASP with path-relinking for the linear ordering problem ⋮ Unnamed Item ⋮ \(d\)-dimensional arrangement revisited ⋮ Distributed balanced partitioning via linear embedding ⋮ An updated survey on the linear ordering problem for weighted or unweighted tournaments ⋮ Subexponential parameterized algorithms and kernelization on almost chordal graphs
