Article

Free access

Trees and Euclidean metrics

Authors:

Nathan Linial,

Avner Magen,

Michael E. SaksAuthors Info & Claims

STOC '98: Proceedings of the thirtieth annual ACM symposium on Theory of computing

Pages 169 - 175

https://doi.org/10.1145/276698.276726

Published: 23 May 1998 Publication History

PDF eReader

References

[1]

L. Bahai and P. Frankl, Linear Algebra Methods in Combinatorics, Preliminary Version 2, Department of Computer Science, The University of Chicago, Chicago, 1992.

Google Scholar

[2]

Y, Bartal, Probabilistic Approximation of metric spaces and its algorithmic applications, 37th IEEE FOCS (1996),184- 193.

Digital Library

Google Scholar

[3]

Y. Bartal, A Blum, C. Butch, A. Tomkins A polylog(n)-competitive algorithm for metrical task systems 29th ACM STOC (1997),711-719

Digital Library

Google Scholar

[4]

J. Bourgain, On Lipschitz embedding of finite metric spaces in Hilbert space, Israel J. Math. 52 (19s5), 46-52.

Crossref

Google Scholar

[5]

J, Bourgain, The metrical interpretation of superreflexivity in Banach spaces, Israel J. Math. 56 (19s6) 222- 230.

Crossref

Google Scholar

[6]

J, Bourgain, T. Figiel and V. Milman, On Hilbertian subsets of finite metric spaces, Israel J. Math. 55 (1986) 147- 152.

Crossref

Google Scholar

[7]

B. Chor, work in progress, 1997.

Google Scholar

[8]

Joseph C. Culberson and P. Rudincki, A fast algorithm for constructing trees from distance matrices, Information Processing Letters 30(1989) 215- 220

Digital Library

Google Scholar

[9]

Michel M.Deza and M. Laurent, Geometry of cuts and metrics, Springer Algorithms and Combinatorics 15

Digital Library

Google Scholar

[10]

M. Linial, N. Linial, N. Tishby and G. Yona, Global self organization of all known protein sequences reveals inherent biological signatures, J. Mol. Biol, 268(1997) 539- 556.

Crossref

Google Scholar

[11]

Jon M.Kleinberg Two Algorithms for Neares~ Neighbor Search in High Dimesions, 29th ACM STOC (1997),599-608.

Digital Library

Google Scholar

[12]

Fundamentals of Molecular Evolution, Sinauer associates, inc.

Google Scholar

[13]

N. Linial, E. London and Yu. Rabinovich, The geometry of graphs and some of its algorithmic applications, Combinatorica, 15(1995) 215- 245.

Crossref

Google Scholar

Cited By

View all

Anil Kumar VMarathe MParthasarathy SSrinivasan A(2009)Scheduling on Unrelated Machines under Tree-Like Precedence ConstraintsAlgorithmica10.1007/s00453-007-9004-y55:1(205-226)Online publication date: 22-May-2009
https://dl.acm.org/doi/10.1007/s00453-007-9004-y
Lua EGriffin TPias MZheng HCrowcroft J(2005)On the accuracy of embeddings for internet coordinate systemsProceedings of the 5th ACM SIGCOMM conference on Internet measurement10.5555/1251086.1251097(11-11)Online publication date: 19-Oct-2005
https://dl.acm.org/doi/10.5555/1251086.1251097
Kumar VMarathe MParthasarathy SSrinivasan A(2005)Scheduling on unrelated machines under tree-like precedence constraintsProceedings of the 8th international workshop on Approximation, Randomization and Combinatorial Optimization Problems, and Proceedings of the 9th international conference on Randamization and Computation: algorithms and techniques10.1007/11538462_13(146-157)Online publication date: 22-Aug-2005
https://dl.acm.org/doi/10.1007/11538462_13
Show More Cited By

Index Terms

Trees and Euclidean metrics
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Trees
  2. Mathematical analysis
    1. Functional analysis
      1. Approximation
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
  2. Randomness, geometry and discrete structures

Recommendations

Metrics on Multilabeled Trees: Interrelationships and Diameter Bounds

Multilabeled trees or MUL-trees, for short, are trees whose leaves are labeled by elements of some nonempty finite set X such that more than one leaf may be labeled by the same element of X. This class of trees includes phylogenetic trees and tree ...
Euclidean Steiner Shallow-Light Trees
SOCG'14: Proceedings of the thirtieth annual symposium on Computational geometry

A spanning tree that simultaneously approximates a shortest-path tree and a minimum spanning tree is called a shallow-light tree (shortly, SLT). More specifically, an (α, β)-SLT of a weighted undirected graph G = (V, E, w) with respect to a designated ...
On the area requirements of Euclidean minimum spanning trees

In their seminal paper on Euclidean minimum spanning trees, Monma and Suri (1992) proved that any tree of maximum degree 5 admits a planar embedding as a Euclidean minimum spanning tree. Their algorithm constructs embeddings with exponential area; ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '98: Proceedings of the thirtieth annual ACM symposium on Theory of computing

May 1998

684 pages

ISBN:0897919629

DOI:10.1145/276698

Chairman:
Jeffrey Vitter

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 May 1998

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC98

Sponsor:

SIGACT

STOC98: The 30th Annual ACM Symposium on Theory of Computing

May 24 - 26, 1998

Texas, Dallas, USA

Acceptance Rates

STOC '98 Paper Acceptance Rate 75 of 169 submissions, 44%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
492
Total Downloads

Downloads (Last 12 months)79
Downloads (Last 6 weeks)12

Reflects downloads up to 26 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Anil Kumar VMarathe MParthasarathy SSrinivasan A(2009)Scheduling on Unrelated Machines under Tree-Like Precedence ConstraintsAlgorithmica10.1007/s00453-007-9004-y55:1(205-226)Online publication date: 22-May-2009
https://dl.acm.org/doi/10.1007/s00453-007-9004-y
Lua EGriffin TPias MZheng HCrowcroft J(2005)On the accuracy of embeddings for internet coordinate systemsProceedings of the 5th ACM SIGCOMM conference on Internet measurement10.5555/1251086.1251097(11-11)Online publication date: 19-Oct-2005
https://dl.acm.org/doi/10.5555/1251086.1251097
Kumar VMarathe MParthasarathy SSrinivasan A(2005)Scheduling on unrelated machines under tree-like precedence constraintsProceedings of the 8th international workshop on Approximation, Randomization and Combinatorial Optimization Problems, and Proceedings of the 9th international conference on Randamization and Computation: algorithms and techniques10.1007/11538462_13(146-157)Online publication date: 22-Aug-2005
https://dl.acm.org/doi/10.1007/11538462_13
Anupam Gupta Amit Kumar Rajeev Rastogi (2003)Exploring the trade-off between label size and stack depth in MPLS routingIEEE INFOCOM 2003. Twenty-second Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE Cat. No.03CH37428)10.1109/INFCOM.2003.1208705(544-554)Online publication date: 2003
https://doi.org/10.1109/INFCOM.2003.1208705
Keselman YShokoufandeh ADemirci MDickinson S(2003)Many-to-many graph matching via metric embedding2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2003. Proceedings.10.1109/CVPR.2003.1211441(I-850-I-857)Online publication date: 2003
https://doi.org/10.1109/CVPR.2003.1211441
Barrière LFraigniaud PSantoro NThilikos D(2003)Searching Is Not JumpingGraph-Theoretic Concepts in Computer Science10.1007/978-3-540-39890-5_4(34-45)Online publication date: 2003
https://doi.org/10.1007/978-3-540-39890-5_4
Gupta AKumar ARastogi R(2001)Traveling with a Pez dispenser (or, routing issues in MPLS)Proceedings 42nd IEEE Symposium on Foundations of Computer Science10.1109/SFCS.2001.959889(148-157)Online publication date: 2001
https://doi.org/10.1109/SFCS.2001.959889
Gupta AShmoys D(2000)Improved bandwidth approximation for treesProceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms10.5555/338219.338640(788-793)Online publication date: 1-Feb-2000
https://dl.acm.org/doi/10.5555/338219.338640
Gupta AVitter JLarmore LLeighton T(1999)Embedding tree metrics into low dimensional Euclidean spacesProceedings of the thirty-first annual ACM symposium on Theory of Computing10.1145/301250.301434(694-700)Online publication date: 1-May-1999
https://dl.acm.org/doi/10.1145/301250.301434

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Metrics on Multilabeled Trees: Interrelationships and Diameter Bounds

Euclidean Steiner Shallow-Light Trees

On the area requirements of Euclidean minimum spanning trees