# Questions tagged [graph-distance]

The tag has no usage guidance.

15 questions
Filter by
Sorted by
Tagged with
61 views

### Distance pairs in labeled directed graph

Suppose we have a simple directed graph with $n$ nodes and $m$ edges, and we label each edge from $1$ to $m$ (with distinct labels). Define the weighted "length" of a directed path to be the maximum ...
90 views

### Voronoi diagram on (weighted) graphs

Suppose I have a graph $G$ (possibly with weights on edges), and I have a subset $S$ of $k$ vertices $s_1, \dotsc, s_k$. I want to solve the post office problem: that is, I want to partition the ...
An easy and quick question: Consider a function $u\in C(\Omega)$, where $\Omega$ is a bounded domain in $\mathbb{R}^n$. Define a function $Q$ that measures the distance of a point $(x,y) \in\mathbb{... 1answer 69 views ### Distance between two polyhedra that takes incidence structure into account Suppose that we have two polyhedra$P_1$and$P_2$in$\mathbb{R}^3$. I would like to define such a metric$\rho(P_1, P_2)$that depends on several factors, but currently I don't know how to do it ... 0answers 363 views ### Graph contained in a metric space I have a metric space$X$and a graph$G=(V,E)$whose set of vertices is a subset$V\subset X$(and$E$is the set of edges, which is a symmetric subset of$V\times V$). For each$v\in V$, the set of ... 1answer 719 views ### Finding the farthest point from a set of other points I have a set of nodes in a very large graph which I call Cluster Points. I also have for each point in the graph, the distance from each point in the Cluster point set. For example: ... 1answer 2k views ### Is the Haversine Formula or the Vincenty's Formula better for calculating distance? Which is better for calculating the distance between two latitude/longitude points, The Haversine Formula or The Vincenty's Formula? Why? The distance is obviously being calculated on Earth. Does ... 0answers 286 views ### Edit distance vs. canonical adjacency matrix distance Let$G$and$G'$be two simple random graphs on the same set of nodes. Let$d_{edit}$be the edit distance between$G$and$G'$. Let$\mathbf{A}$and$\mathbf{A'}$be the adjacency matrices of the ... 0answers 130 views ### Of the standard distance metrics, which ones can/cannot be embedded in Euclidean space? Given the discussion from: Representability of finite metric spaces it appears that a 1974 paper by Morgan gives the criteria for when a distance metric can be embedded in Euclidean space. My first ... 0answers 2k views ### Possible ways to create a graph representation from a distance matrix (through approximation) Forgive me, Im not math professional, but a computer scientist at the beginning of my base research from my thesis, so bare with me if I miss something blatantly obvious. I have a Euclidean distance ... 0answers 71 views ### Looking for similar centrality measurement on graph I'm working on a graph problem somehow related to centrality measurement. Given an undirected, unweighted tree$T$and a vertex$v$, let$D_i(v)$be the set of vertices in$T$that are i hops from$v$,... 1answer 189 views ### planar bipartite cubic graph Suppose we have a cubic planar bipartite graph with no double edges. I am looking for a statement about the minimal distance between the square faces (shortest path from a vertex on the first square ... 3answers 3k views ### Distance between two networks Suppose you have networks A and B, each with a set of nodes and edges. You want to measure how similar the networks are to each-other. None of the nodes or edges are labelled. What are the metric(s) ... 1answer 234 views ### Graphs with circulant distance matrices The cycle has this property. For instance, the distance matrix for a 6-cycle is:$A=\begin{bmatrix} 0 & 1 & 2 & 3 & 2 & 1 \\\\ 1 & 0 & 1 &...
If $G$ is a graph with distance function $d(x,y)$ between vertices, the transmission of a vertex $x \in v(G)$ is defined as $\sigma_{x}=\sum_{y \neq x}{d(x,y)}$. I want to know if there is a known ...