Edge ranking and searching in partial orders

DOI10.1016/j.dam.2008.03.007zbMath1152.68014OpenAlexW2064883689MaRDI QIDQ955315

Dariusz Dereniowski

Publication date: 19 November 2008

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2008.03.007

zbMATH Keywords

posetspanning treegraph searchingdagedge ranking

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Partial orders, general (06A06) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (12)

List rankings and on-line list rankings of graphs ⋮ On the tree search problem with non-uniform costs ⋮ Searching for quicksand ideals in partially ordered sets ⋮ On the complexity of searching in trees and partially ordered structures ⋮ Improved approximation algorithms for the average-case tree searching problem ⋮ Binary search in graphs revisited ⋮ The binary identification problem for weighted trees ⋮ The complexity of bicriteria tree-depth ⋮ The complexity of bicriteria tree-depth ⋮ On the Tree Search Problem with Non-uniform Costs ⋮ Binary Search in Graphs Revisited ⋮ An efficient noisy binary search in graphs via Median approximation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimal node ranking of trees
• Edge ranking of graphs is hard
• Edge ranking of weighted trees
• On Minimum Edge Ranking Spanning Trees
• Searching ordered structures
• Optimal Search in Trees
• Approximation algorithms for finding low-degree subgraphs
• Minimum average cost testing for partially ordered components

This page was built for publication: Edge ranking and searching in partial orders