Ordering a Sparse Graph to Minimize the Sum of Right Ends of Edges

DOI10.1007/978-3-030-48966-3_17OpenAlexW3032040206MaRDI QIDQ5041192

Peter Damaschke

Publication date: 13 October 2022

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-48966-3_17

zbMATH Keywords

treecycleminimum linear arrangementelimination orderingdynamic programming on subsets2-core3-corepick-by-order

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Discrete mathematics in relation to computer science (68Rxx)

Related Items (1)

On an ordering problem in weighted hypergraphs

Cites Work

• Exact exponential algorithms.
• An improved approximation ratio for the minimum linear arrangement problem
• Parameterized algorithmics for linear arrangement problems
• A new rounding procedure for the assignment problem with applications to dense graph arrangement problems
• The deterministic product location problem under a pick-by-order policy
• Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut
• Approximation Guarantees for the Minimum Linear Arrangement Problem by Higher Eigenvalues
• Minimum Linear Arrangement of Series-Parallel Graphs
• Tractable Parameterizations for the Minimum Linear Arrangement Problem
• A Correction on Shiloach's Algorithm for Minimum Linear Arrangement of Trees
• Optimal Linear Arrangement of Interval Graphs
• Unnamed Item
• Unnamed Item

This page was built for publication: Ordering a Sparse Graph to Minimize the Sum of Right Ends of Edges