Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with graph-theory
Search options not deleted
user 31310
Questions about the branch of combinatorics called graph theory (not to be used for questions concerning the graph of a function). This tag can be further specialized via using it in combination with more specialized tags such as extremal-graph-theory, spectral-graph-theory, algebraic-graph-theory, topological-graph-theory, random-graphs, graph-colorings and several others.
1
vote
All pairs shortest path with maximum distance
Interpreting your question that you want to find the shortest paths in order of increasing length, then a nested Dijkstra algorithm may solve your problem also in case of directed graphs.
I assume you …
- 13.2k
1
vote
All pairs shortest path with maximum distance
maybe this paper, in which the calculation of the all pairs shortest paths in $O(n^2)$ with high probability is solved, meets your requirements.
Some preconditions about the distribution of edge lengt …
- 13.2k
1
vote
1
answer
267
views
History of the Vertex Disjoint Cycle Cover with Minimal Edgeweight Sum
Questions:
who first posed the problem of determining a collection of (directed) cycles, whose edgeweight sum is minimal and, for which each vertex belongs to exactly one of the cycles?
who came up …
- 13.2k
2
votes
0
answers
28
views
Graph of the optimal spanning trees of a complete weighted graph
Given a complete weighted graph $G(V,E);\ E=\lbrace\lbrace u,v\rbrace\,|\,u,v\in V\rbrace$, the set $\mathbb{T}$ of the spanning trees of $G$ is the disjoint union of sets of spanning trees, whose und …
- 13.2k
1
vote
3-coloring of specific planar graphs
a different approach would be to consider a planar embedding of the graph G into the euclidean plane and then proceed as follows:
as long as there are pairs of odd "faces" with a common edge (i.e. cy …
- 13.2k
1
vote
History of the Vertex Disjoint Cycle Cover with Minimal Edgeweight Sum
I just found an online publication related to the problem: "The Cycle Cover Problem" by J.L. Szwarcfiter and B.L. Wilson, Technical Report No 131 1979, University of Newcastle upon Tyne, UK.
As tha …
- 13.2k
0
votes
1
answer
37
views
Graph connectivity after deleting an f-factor
Let $G(V,E)$ be an undirekted $k$-vertex-connected, $k$-regular graph
and let $F$ be an $f$-factor of $G$ consisting of a set of $f$-vertex-connected components, $f<k$.
Question:
what is the v …
- 13.2k
1
vote
3
answers
109
views
Freely accessible collections of graph data
This question aims at providing links to definitions of graphs that either come from real-world problem or research that can be accessed and used freely; good examples in that vein are TSPLIB95 or the …
- 13.2k
1
vote
Minimally 2-vertex-connected graphs?
I conjecture that a a sufficient condition for a graph being minimally 2-vertex-connected is that
it is $2$-vertex-connected and if every vertex $u$ is adjacent to some vertex $v$ of degree $2$ and c …
- 13.2k
11
votes
1
answer
390
views
Shortest Paths in the "Cantor Graph"
First, let me explain, what I understand by a "Cantor Graph":
it is an infinite, directed graph with self loops and countably many vertices labelled with the natural numbers; every ordered pair of …
- 13.2k
0
votes
Minimally 2-vertex-connected graphs?
$K_3$ is the only graph with a triangle that contains a bivalent vertex, and is a minimally vertex 2-connected graph (MV2CG).
According to the two ears theorem every triangulated polygon with at least …
- 13.2k
1
vote
Is there an algorithm for generating sets of routes that satisfy edge volume constraints?
At the very lowest level of modelling, one has to make some assumptions about the chosen paths, e.g. that they are the optimal ones connecting a pair of nodes.
With that assumption, one obtains for ea …
- 13.2k
1
vote
Alternative parallel paths
the answer is yes, simply because there are at least two different paths for $n\ge 2$.
Assuming that at least two different paths exist for $n\ge 2$ one can interpret the 1st path as a $0$bit and the …
- 13.2k
3
votes
Shortest path in a weighted graph with coloured edges
The problem can be reduced to an ordinary shortest path problem via vertex splitting where however, the number of generated vertices equals the degree of the original vertex and not two, as is commonl …
- 13.2k
1
vote
0
answers
125
views
Pitfalls with modeling problems as graphs
The motivation for this question is that I could solve problem by extracting a graph structure from it and then applying a standard graph-algorithm and transfering the solution back to the interpretat …
- 13.2k