|
Journal of Automata, Languages and Combinatorics
formerly:
Journal of Information Processing and Cybernetics /
Elektronische Informationsverarbeitung und Kybernetik
|
|
@article{jalc010101,
author = {Peter J. Grabner and Helmut Prodinger},
title = {On the Optimality of an Algorithm of Reingold and Supowit},
journal = jalc,
year = 1996,
volume = 1,
number = 1,
pages = {5--11},
keywords = {matching, cost, divide-and-conquer heuristic,
average-case analysis, Rice's method},
abstract = {Reingold and Supowit have analyzed a divide-and-conquer
heuristic to obtain a matching with a small cost. In this
paper we show that --- among a large class of similar
strategies --- the version of Reingold and Supowit
produces the minimal expected costs.}
}