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

DOI10.1051/ro/2015024zbMath1338.90254OpenAlexW2308641315MaRDI QIDQ2805488

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)

Related Items (2)

Evaluating topological ordering in directed acyclic graphs ⋮ Linear time algorithms on mirror trees

Cites Work

• Unnamed Item
• Simple linear time recognition of unit interval graphs
• On optimal linear arrangements of trees
• An updated survey on the linear ordering problem for weighted or unweighted tournaments
• Optimality of HLF for scheduling divide-and-conquer UET task graphs on identical parallel processors
• A polynomial algorithm for minDSC on a subclass of series Parallel graphs
• The Recognition of Series Parallel Digraphs
• Optimal Linear Ordering
• Optimal Linear Arrangement of Interval Graphs

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