Journal article icon

Journal article

On equicut graphs

Abstract:

The size sz(G) of an l_1-graph G=(V,E) is the minimum of n_f/t_f over all its possible l_1-embeddings f into n_f-dimensional hypercube with scale t_f. In terms of v=|V|, the sum of distances between all the pairs of vertices of G is at most sz(G) v^2/4 for v even, (resp. sz(G)(v-1)(v+1)/4 for v odd). This bound is reached if and only if G is an equicut graph, that is, G admits an l_1-embedding with column sums v/2, v even (resp. (v-1)/2 for v odd). Basic properties of equicut graphs are inv...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
Publisher:
Taylor and Francis Publisher's website
Journal:
Multiple Valued Logic: An International Journal
Volume:
7
Pages:
363–377
Publication date:
2001-01-01
ISSN:
1023-6627
Source identifiers:
446351
Keywords:
Pubs id:
pubs:446351
UUID:
uuid:f619d170-0c01-4127-80cd-98067925b4ff
Local pid:
info:fedora/pubs:446351
Deposit date:
2016-07-28

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP