Optimal edge ranking of trees in polynomial time

DOI10.1007/BF01189071zbMath0826.68093MaRDI QIDQ1892584

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

Publication date: 19 June 1995

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

trees; edge ranking; height edge-separator tree

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

68M20: Performance evaluation, queueing, and scheduling in the context of computer systems

Related Items

Forbidden graphs for tree-depth, On the complexity of searching in trees and partially ordered structures, LIFO-search: a min-max theorem and a searching game for cycle-rank and tree-depth, Minimum edge ranking spanning trees of split graphs, NP-hardness proof and an approximation algorithm for the minimum vertex ranking spanning tree problem, Optimal vertex ranking of block graphs, Edge ranking of graphs is hard, Algorithms for generalized vertex-rankings of partial k-trees, The binary identification problem for weighted trees, On the vertex ranking problem for trapezoid, circular-arc and other graphs, A polynomial time algorithm for obtaining minimum edge ranking on two-connected outerplanar graphs, Edge ranking of weighted trees

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