Edge ranking and searching in partial orders
From MaRDI portal
Publication:955315
DOI10.1016/j.dam.2008.03.007zbMath1152.68014MaRDI QIDQ955315
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
68Q25: Analysis of algorithms and problem complexity
06A06: Partial orders, general
68P10: Searching and sorting
68R10: Graph theory (including graph drawing) in computer science
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Searching for quicksand ideals in partially ordered sets, Binary Search in Graphs Revisited, The complexity of bicriteria tree-depth, The complexity of bicriteria tree-depth, List rankings and on-line list rankings of graphs, On the tree search problem with non-uniform costs, Improved approximation algorithms for the average-case tree searching problem, On the complexity of searching in trees and partially ordered structures, Binary search in graphs revisited, The binary identification problem for weighted trees, An efficient noisy binary search in graphs via Median approximation, On the Tree Search Problem with Non-uniform Costs
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
