Linear time algorithms to solve the linear ordering problem for oriented tree based graphs

DOI10.1051/RO/2015024MaRDI QIDQ2805488zbMATH OpenOpenAlexFDO

Authors Alain Quilliot, Djamal Rebaine

Publication date 11 May 2016

Published in RAIRO. Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1051/ro/2015024

zbMATH Keywords

linear time algorithmsdirected treelinear orderingdivide-and-conquer graphs

Mathematics Subject Classification ID

Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Recommendations

• Efficient local search algorithms for the linear ordering problem
• Multilevel algorithms for linear ordering problems
• scientific article; zbMATH DE number 3902051
• On optimal linear arrangements of trees
• A Cutting Plane Algorithm for the Linear Ordering Problem

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A polynomial algorithm for minDSC on a subclass of series Parallel graphs
• An updated survey on the linear ordering problem for weighted or unweighted tournaments
• On optimal linear arrangements of trees
• Optimal Linear Arrangement of Interval Graphs
• Optimal Linear Ordering
• Optimality of HLF for scheduling divide-and-conquer UET task graphs on identical parallel processors
• Simple linear time recognition of unit interval graphs
• The Recognition of Series Parallel Digraphs

Cited in

(5)

• Evaluating topological ordering in directed acyclic graphs
• Multilevel algorithms for linear ordering problems
• On the complexity of a linear ordering of weighted directed acyclic graphs
• Efficient local search algorithms for the linear ordering problem
• Linear time algorithms on mirror trees

This page was built for publication: Linear time algorithms to solve the linear ordering problem for oriented tree based graphs

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