ISSN:
1433-0490
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Abstract LetM be anm-by-n matrix with entries in {0,1,⋯,K}. LetC(M) denote the minimum possible number of edges in a directed graph in which (1) there arem distinguished vertices calledinputs, andn other distinguished vertices calledoutputs; (2) there is no directed path from an input to another input, from an output to another output, or from an output to an input; and (3) for all 1 ≤i ≤m and 1 ≤j ≤n, the number of directed paths from thei-th input to thej-th output is equal to the (i,j)-th entry ofM. LetC(m,n,K) denote the maximum ofC(M) over allm-by-n matricesM with entries in {0,1,⋯,K}. We assume (without loss of generality) thatm ≥n, and show that ifm=(K+1) 0(n) andK=22 0(m) , thenC(m,n,K)= H/logH + 0(H/logH), whereH=mnlog(K + 1) and all logarithms have base 2. The proof involves an interesting problem of Diophantine approximation, which is solved by means of an unusual continued fraction expansion.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01776581
Permalink