Abstract In 1971, Graham and Pollack established a relationship between the number of
negative eigenvalues of the distance matrix and the addressing problem in data …

Cuts and metrics are well-known objects that arise-independently, but with many deep and
fascinating connections-in diverse fields: in graph theory, combinatorial optimization …

XII Preface solution as efficiently as possible. Most of the problems we treat have a good
algorithmic solution, but we also show how even difficult problems can be treated (for …

Phylogenetic combinatorics is a branch of discrete applied mathematics concerned with the
combinatorial description and analysis of phylogenetic trees and related mathematical …

Graph realizations of finite metric spaces have widespread applications, for example, in
biology, economics, and information theory. The main results of this paper are: 1. Finding …

Network realization problems require, given a specification π for some network parameter
(such as degrees, distances or connectivity), to construct a network G conforming to π, or to …

Abstract A map** α: V (G)→ V (H) from the vertex set of one graph G to another graph H is
an isometric embedding if the shortest path distance between any two vertices in G equals …

The problem of realizing finite metric spaces in terms of weighted graphs has many
applications. For example, the mathematical and computational properties of metrics that …

It is shown that the problem of realizing a metric by a graph or network with minimum total
edge-length is, depending on the version, NP-hard or NP-complete. In particular, Discrete …

Tropical geometry is a relatively new field of mathematics that studies the tropicalization
map: a map that assigns a certain type of polyhedral complex, called a tropical variety, to an …