All Questions
93
questions
-1
votes
0
answers
32
views
Fixed quantities in Big O notation
Consider the following description of a random graph generation algorithm with parameters $n$ (number of vertices) and $m$ (number of edges).
All iterations add an edge except those where a ...
- 3,468
0
votes
1
answer
49
views
A proof for the statement: The 3-Dimensional matching problem is NP-Complete
The 3-Dimensional Matching Problem is relatively well known in the fields of discrete mathematics and computer science. The problem consists of determining whether a tripartite
$3$-hypergraph with ...
- 3,468
0
votes
1
answer
49
views
Proof that if a graph has edge connectivity 3, then the girth is bounded by the number of nodes divided by two + 1, g(G) <= |V(G)| / 2 + 1
I've not been able to solve this problem for a week now. My idea was that I start with a circle with n nodes and because the edge connectivity is 3, every node must have at least 3 neighbours, so to ...
- 11
0
votes
0
answers
39
views
What is the asymptotically best algorithm for the euclidean Steiner tree problem?
So I would like to know what the fastest (asymptotically, worst case runtime) exact algorithm for the Euclidean Steiner tree problem is. (More precisely, I would like to know the best known algorithm ...
- 131
3
votes
0
answers
49
views
Inequalities for sum of $k$ smallest degrees of a graph
As part of a homework assignment, I am doing a proof for a generalised variant of Karger's algorithm and am stuck at a particular step. I have proven that for a graph $G=(V,E)$ [writing $n=|V|$] with ...
- 55
2
votes
3
answers
82
views
Generalization of independent set to distance at least 3
We know that in graph theory, an independent set is a set of vertices, such that no two of which are adjacent. There is rich theory about independent set, including approximation algorithm for finding ...
- 166
0
votes
1
answer
31
views
How to find the location of an object moving through a graph with inputs of arcs?
I have a bidirected graph which represents rooms in a building. I have scanners set up on doorways which can detect an object moving through them (but not direction). Based on this information what ...
0
votes
1
answer
34
views
Condition for a Hamiltonian cycle existing proof question
Let $G$ be a graph. If there exists $X\subseteq V(G)$, $X\neq \emptyset$ s.t. $G\setminus X$ has more than $|X|$ components, then $G$ has no Hamiltonian cycle.
Proof.
Suppose for a contradiction that $...
- 2,971
1
vote
1
answer
169
views
Valid placement of pebbles on board. Graph theory problem that everyone in my class got wrong [duplicate]
Can someone please help with this? I’ve worked on it for a few hours but can’t come up with a proof. Thanks!
Consider a $2n\times 2n$ board (namely a board with $2n$ rows and $2n$ columns for a total ...
- 19
7
votes
1
answer
822
views
diameter and radius in graph and disconnected graph
We have an undirected Graph $G$.
Def $1$: The diameter of a graph is defined as the maximum of shortest paths between two vertices of $G$.
Def $2$: we define $L(S)$ as maximum length of shortest paths ...
1
vote
1
answer
207
views
two asymptotic comparison on sparse graph and misunderstanding point
I read in my notes:
if we use Dijkstra $|V|$ times ($|V|$ number of vertexes) for finding all pairs shortest paths in graph $G$, We get time complexity for Dijkstra algorithm as $O(VE+ V^2 log V)$ and ...
- 63
1
vote
1
answer
100
views
shortest path not changed if one of formula is used to update all weights
Weighted Directed Graph $G$ is given. there is no negative cycle. vertexes number is $1$ to $n$. weight of edge $a$ to $b$ is $P(a,b)$. $G'$ is graph $G$ with edges will be changed according to ...
- 324
1
vote
1
answer
62
views
relation according to height factor between two specific trees
I have $2$ trees as follows:
$First$
$Second$
I want to find a relation between these two trees, I need this relation: if we get height of the second three as $H$ what is the relation between $...
- 324
2
votes
1
answer
91
views
Determine the smallest $k$ for which a graph is k-partite.
A graph $G=(V,E)$ is said to be $k$-partite if you can partition all of the vertices of $G$ into independent sets. However, is there a way to determine the minimum value of $k$? Suppose that $G$ is 4-...
- 1,928
1
vote
1
answer
331
views
Is this graph theory proof correct?
Source
Question:
In this problem, we describe a faster algorithm, due to Hopcroft and Karp, for finding a maximum matching in a bipartite graph. The algorithm runs in O($\sqrt V E$) time. Given an ...
