scientific article; zbMATH DE number 1535253

zbMATH Open0949.68545MaRDI QIDQ4515740FDOQ4515740

Authors: Nicholas Pippenger 

Publication date: 23 November 2000

Title of this publication is not available (Why is that?)

Recommendations

• scientific article; zbMATH DE number 1334210
• Average-case complexity of single-source shortest-paths algorithms: lower and upper bounds
• Average-Case Lower Bounds for Searching
• On the complexity of searching in trees: average-case minimization
• scientific article; zbMATH DE number 1416161
• The average complexity of depth-first search with backtracking and cutoff
• Improved approximation algorithms for the average-case tree searching problem
• Technical Note—The Complexity of the Optimal Searcher Path Problem
• Rudiments of an average case complexity theory for piecewise-linear path following algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial probability (60C05) Applications of graph theory to circuits and networks (94C15) Network design and communication in computer systems (68M10)

Cited In (6)

• Average-Case Lower Bounds for Searching
• Local versus global search in channel graphs
• The average complexity of depth-first search with backtracking and cutoff
• Improved approximation algorithms for the average-case tree searching problem
• Average-case analysis of best-first search in two representative directed acyclic graphs
• On the average length of lexicographic paths

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4515740)