Access Restriction

Author Hwang, F. K. ♦ Deutsch, D. N.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1973
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract Suppose we are given two disjoint linearly ordered subsets $\textit{A}$ and $\textit{B}$ of a linearly ordered set $\textit{C},$ say $\textit{A}$ = ${\textit{a}1$ < $\textit{a}2$ < ··· < $\textit{am}}$ and $\textit{B}$ = ${\textit{b}1$ < $\textit{b}2$ < ··· < $\textit{bn}}.$ The problem is to determine the linear ordering of their union (i.e. to merge $\textit{A}$ and $\textit{B})$ by means of a sequence of pairwise comparisons between an element of $\textit{A}$ and an element of $\textit{B}$ (which we refer to in the paper as the (m, n) problem). Given any algorithm $\textit{s}$ to solve the (m, n) problem, we are interested in the maximum number of comparisons $\textit{Ks}(\textit{m,$ n) required under all possible orderings of $\textit{A}$ ∪ $\textit{B}.$ An algorithm $\textit{s}$ is said to be minimax if $\textit{Ks}(\textit{m,$ n) = $\textit{K}(\textit{m,$ n) where $\textit{K}(\textit{m,$ n) = mins $\textit{Ks}(\textit{m,$ n)It is a rather difficult task to determine $\textit{K}(\textit{m,$ n) in general. In this study the authors are only concerned with the minimax over a particular class of merging algorithms. This class includes the tape merge algorithm, the simple binary algorithm, and the generalized binary algorithm.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1973-01-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 20
Issue Number 1
Page Count 12
Starting Page 148
Ending Page 159

Open content in new tab

   Open content in new tab
Source: ACM Digital Library