DIMACS TR: 2002-53
A Note on Linear Discrepancy and Bandwidth
Authors: Dieter Rautenbach
ABSTRACT
Fishburn, Tanenbaum and Trenk \cite{FTT01a}
define the linear discrepancy ${\rm ld}(P)$ of a poset $P=(V,<_P)$
as the minimum integer $k\geq 0$
for which there exists a bijection $f:V\to\{ 1,2,\ldots,|V|\}$
such that $u<_P v$ implies $f(u) < f(v)$
and $u||_P v$ implies $|f(u)-f(v)|\leq k$.
In \cite{FTT01b} they prove that the linear discrepancy of
a poset equals the bandwidth of its cocomparability graph.
Here we provide partial solutions to some problems formulated
in \cite{FTT01a} about the linear discrepancy and the bandwidth
of cocomparability graphs.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2002/2002-53.ps.gz
DIMACS Home Page