Searching in Trees, Series-Parallel and Interval Orders

DOI10.1137/0215077zbMath0619.68057OpenAlexW2070004158WikidataQ116185938 ScholiaQ116185938MaRDI QIDQ3756532

Ulrich Faigle, György Turán, László Lovász, Rainer Schrader

Publication date: 1986

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0215077

zbMATH Keywords

interval ordersseries-parallel orderssearching trees

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Partial orders, general (06A06) Searching and sorting (68P10)

Related Items

On complexity of maximizatin of submodular functions^*, On the computational complexity of the order polynomial, Understanding the generalized median stable matchings, On the complexity of dynamic programming for sequencing problems with precedence constraints, On the complexity of searching in trees and partially ordered structures, Improved approximation algorithms for the average-case tree searching problem, Cross-series-parallel digraphs, On estimating the number of order ideals in partial orders, with some applications, Algorithmic combinatorics based on slicing posets, Series-parallel posets and the Tutte polynomial, On Generalized Comparison-Based Sorting Problems