Optimal edge ranking of trees in polynomial time

DOI10.1007/BF01189071zbMath0826.68093OpenAlexW2079306236MaRDI QIDQ1892584

Alejandro A. Schäffer, Pilar de la Torre, Raymond Greenlaw

Publication date: 19 June 1995

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01189071

zbMATH Keywords

treesedge rankingheight edge-separator tree

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (23)

On Dasgupta's hierarchical clustering objective and its relation to other graph parameters ⋮ On the tree search problem with non-uniform costs ⋮ A polynomial time algorithm for obtaining minimum edge ranking on two-connected outerplanar graphs ⋮ Minimum edge ranking spanning trees of split graphs ⋮ NP-hardness proof and an approximation algorithm for the minimum vertex ranking spanning tree problem ⋮ Edge ranking of graphs is hard ⋮ Forbidden graphs for tree-depth ⋮ \(l_p\)-optimal rankings and max-optimal rankings are different ⋮ Finding the edge ranking number through vertex partitions ⋮ On the vertex ranking problem for trapezoid, circular-arc and other graphs ⋮ On the complexity of searching in trees and partially ordered structures ⋮ Improved approximation algorithms for the average-case tree searching problem ⋮ Facial edge ranking of plane graphs ⋮ Optimal vertex ranking of block graphs ⋮ The binary identification problem for weighted trees ⋮ Edge ranking of weighted trees ⋮ LIFO-search: a min-max theorem and a searching game for cycle-rank and tree-depth ⋮ The complexity of bicriteria tree-depth ⋮ The complexity of bicriteria tree-depth ⋮ Conflict-free connection of trees ⋮ On the Tree Search Problem with Non-uniform Costs ⋮ Algorithms for generalized vertex-rankings of partial k-trees ⋮ Obstructions for Tree-depth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On an edge ranking problem of trees and graphs
• Optimal node ranking of trees
• The node-deletion problem for hereditary properties is NP-complete
• On the complexity of edge labelings for trees
• The maximum flow problem is log space complete for P
• Optimal node ranking of tree in linear time
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Parallel Merge Sort
• Edge-Deletion Problems
• Node-Deletion Problems on Bipartite Graphs
• The Parallel Evaluation of General Arithmetic Expressions

This page was built for publication: Optimal edge ranking of trees in polynomial time