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

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

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

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

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)

Cites Work

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

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)