Parameterized algorithmics for linear arrangement problems

DOI10.1016/j.dam.2008.05.008zbMath1178.68376OpenAlexW1988217358MaRDI QIDQ1003461

Henning Fernau

Publication date: 4 March 2009

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2008.05.008

zbMATH Keywords

parameterized algorithmslinear arrangement problems

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (9)

Ordering a Sparse Graph to Minimize the Sum of Right Ends of Edges ⋮ Smaller Kernels for Several FPT Problems Based on Simple Observations ⋮ Faster deterministic algorithm for \textsc{Co-Path Set} ⋮ On a binary distance model for the minimum linear arrangement problem ⋮ Improved kernel results for some FPT problems based on simple observations ⋮ Parameterized algorithms for \(d\)-hitting set: the weighted case ⋮ Approximation and fixed-parameter algorithms for consecutive ones submatrix problems ⋮ Minimum leaf out-branching and related problems ⋮ On an ordering problem in weighted hypergraphs

Uses Software

• LOLIB

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Some simplified NP-complete graph problems
• Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT.
• Applications of the crossing number
• Two-Layer Planarization: Improving on Parameterized Algorithmics
• The Linear Arrangement Problem Parameterized Above Guaranteed Value
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Optimal Numberings of an $N \times N$ Array
• Parameterized complexity: exponential speed-up for planar graph problems
• Optimal Linear Ordering
• Mathematical Foundations of Computer Science 2004
• Experiments on the minimum linear arrangement problem
• Graph Drawing
• SOFSEM 2006: Theory and Practice of Computer Science
• SOFSEM 2006: Theory and Practice of Computer Science

This page was built for publication: Parameterized algorithmics for linear arrangement problems