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 126667
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.
3
votes
Accepted
Given a Spanning Tree and an Edge Not on the Spanning Tree, How to Form a Cycle Base?
I think you're likely to get better answers if you post this question on Stack Overflow rather than here.
But anyways, if your graph doesn't have weights on edges, you don't need Kruskal's algorithm …
- 25.2k
7
votes
Edge-disjoint shortest paths
Yes. Just pick the two paths (not necessarily edge disjoint) in G of shortest total length which together join the four vertices into two pairs. If they contained a common edge, you could remove tha …
- 25.2k
6
votes
Number of paths equal less than equal to a certain length
This problem seems to be NP-hard, in an informal sense. I'll sketch how we could use an algorithm for this problem to solve the knapsack problem. Suppose given $n$ objects with weights $w_1$, ..., $ …
- 25.2k
8
votes
Accepted
Is there a free digraph associated to a graph?
I like to use the following definitions, which give a nonstandard definition of undirected graph but produce particularly nice categories.
A directed graph is a pair of sets V and E together with …
- 25.2k
4
votes
Connecting $2n$ points in $\mathbb R^2$ with line segments s.t. each point belongs to exactl...
@RobPratt's answer describes a good general-purpose approach. The specific case where edge weights are given by Euclidean distances is also a well-studied problem. The paper A Divide-and-Conquer Algor …
- 25.2k