TY - JOUR
T1 - Recognizing median graphs in subquadratic time
AU - Hagauer, Johann
AU - Imrich, Wilfried
AU - Klavžar, Sandi
PY - 1999/2/28
Y1 - 1999/2/28
N2 - Motivated by a dynamic location problem for graphs, Chung, Graham and Saks introduced a graph parameter called windex. Graphs of windex 2 turned out to be, in graph-theoretic language, retracts of hypercubes. These graphs are also known as median graphs and can be characterized as partial binary Hamming graphs satisfying a convexity condition. In this paper an O(n3/2 log n) algorithm is presented to recognize these graphs. As a by-product we are also able to isometrically embed median graphs in hypercubes in O(m log n) time.
AB - Motivated by a dynamic location problem for graphs, Chung, Graham and Saks introduced a graph parameter called windex. Graphs of windex 2 turned out to be, in graph-theoretic language, retracts of hypercubes. These graphs are also known as median graphs and can be characterized as partial binary Hamming graphs satisfying a convexity condition. In this paper an O(n3/2 log n) algorithm is presented to recognize these graphs. As a by-product we are also able to isometrically embed median graphs in hypercubes in O(m log n) time.
UR - https://www.scopus.com/pages/publications/0011324625
U2 - 10.1016/S0304-3975(97)00136-9
DO - 10.1016/S0304-3975(97)00136-9
M3 - Article
AN - SCOPUS:0011324625
SN - 0304-3975
VL - 215.1999
SP - 123
EP - 136
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 1-2
ER -