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
Version:
Author's Original

Actions


Access Document


Files:

Authors


More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Computer Science
Publisher:
Taylor & Francis Ltd Publisher's website
Journal:
Multiple Valued Logic: An International Journal
Volume:
7
Pages:
363–377
Publication date:
2001
ISSN:
1023-6627
URN:
pubs:f619d170-0c01-4127-80cd-98067925b4ff
Source identifiers:
446351
Local pid:
info:fedora/pubs:446351

Terms of use


Metrics



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

TO TOP