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

DOI10.1007/978-3-030-48966-3_17MaRDI QIDQ5041192zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Minimum flow time graph ordering.
• Optimal vertex ordering of graphs
• scientific article; zbMATH DE number 1303559
• scientific article; zbMATH DE number 4047762
• scientific article; zbMATH DE number 1560506

Cites work

• scientific article; zbMATH DE number 4043771 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A correction on Shiloach's algorithm for minimum linear arrangement of trees
• A new rounding procedure for the assignment problem with applications to dense graph arrangement problems
• An improved approximation ratio for the minimum linear arrangement problem
• Approximation Guarantees for the Minimum Linear Arrangement Problem by Higher Eigenvalues
• Exact exponential algorithms.
• Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut
• Minimum Linear Arrangement of Series-Parallel Graphs
• Optimal Linear Arrangement of Interval Graphs
• Parameterized algorithmics for linear arrangement problems
• The deterministic product location problem under a pick-by-order policy
• Tractable parameterizations for the minimum linear arrangement problem

Cited in

(1)

• On an ordering problem in weighted hypergraphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5041192)