New answers tagged graphs
1
A minimum weight edge is an edge whose weight is minimal among all edges. There can be more than one minimum weight edge. All minimum weight edges have the same weight.
Similarly, a minimum spanning tree is a spanning tree whose weight is minimal among all spanning trees. There can be more than one minimum spanning tree. All minimum spanning trees have the ...
1
Find the set $L$ containing the $\ell$ extra edges (actually, find any set $L$ of $\ell$ edges such that $G-L$ is a tree).
Let $C$ be an optimal solution.
For each edge $(u,v)$ in $L$, guess whether $u \in C$. If you guess "yes", add $u$ to a set $X$, otherwise add $v$ to $X$.
(Notice that it is possible for both $u$ and $v$ to be in $C$, but we do ...
2
As you probably know, $A^i_{st}$ is the total weight of walks of length $i$ from $s$ to $t$. Since
$$
\sum_{i=0}^k (xA)^i = \sum_{i=0}^k A^i x^i,
$$
the $s,t$ coefficient of $A_{G'}$ is
$$
\sum_{i=0}^k A^i_{st} x^i.
$$
This is a polynomial in which for $0 \leq i \leq k$, the coefficient of $x^i$ is the total weight of walks of length $i$ from $s$ to $t$.
0
You could take the Delaunay triangulation of a random set of points (or, if you want almost lattices, a perturbation of something regularly defined) and remove some edges if you want.
This won't give you a small-world graph, but no lattice-like thing would. If you want something like this, you'll have to have some fractal properties anyway (if the ...
4
A search algorithm is a recursive procedure which accepts an instance and a partial solution and attempts to extend it to a complete solution bit by bit. For example, consider a search algorithm trying to solve the eight queens puzzle. The search is initiated with an empty board. On any given position, the search algorithm attempts to place one more queen, ...
0
Though this is from 4 years ago, another way to solve this is by finding the Hamiltonian Path of the Line Graph of G. Just convert each edge to a vertex and connect those vertices if the corresponding edges shared a vertex in G. (Respecting the directions in this case.)
So the line graph would look like this, each vertex is labeled with the direction of the ...
1
The algorithm to compute $G'$ is really easy: just return $G$.
Indeed, given any $G=(V,E)$ the only graph $G'=(V, E')$ such that $U \subseteq V$ is a vertex cover of $G$ iff $U$ is a vertex cover of $G'$ is $G$ itself.
To prove this you can show that we must simultaneously have $E \subseteq E'$ and $E' \subseteq E$.
Proof that $E \subseteq E'$: Suppose ...
0
Here is an example when for k being the inner most loop doesn't work:
0 -- 2 -- 3 -- 1
Say each edge weight is 1. The corresponding adjacency matrix is:
Node
0
1
2
3
0
0
inf
1
inf
1
inf
0
inf
1
2
1
inf
0
1
3
inf
1
1
0
The final distance for 0 and 1 is inf, which is incorrect:
dist[0][1] = min(inf, dist[0][1]+dist[1][1], dist[0][2]+dist[2][1], dist[0][3]...
1
Work In progress.
Feel free to contribute filling up the arguments that are incomplete.
Definitions:
Before proving anything we need to make it precise what is it what we are trying to prove.
Planar graph: A graph that can be embedded in $\mathbb{R}^2$.(1)
Plane graph: A planar graph together with a particular embedding $G\hookrightarrow\mathbb{R}^2$. I ...
0
You can probably locate a copy of Bondy and Murty's book Graph Theory with its Applications. While they don't prove it either, they give the following intuition:
Let $G$ be a (connected) plane graph and $G^*$ its dual. There is a natural embedding of $G^*$ in the plane that corresponds to $G$, namely that each vertex $f^*$ in $G^*$ is placed in the ...
1
Use a priority queue to keep a list of all vertices with prioritization on in-degrees.
Pop off one vertex $v$ with in-degree zero, decrement the in-degree-count of the out-neighborhood of $v$.
Repeat until empty.
If the input graph is a DAG, this will give you a topological ordering.
1
Just to clarify your doubt. An online algorithm is an algorithm that does not have the whole input (otherwise it would be offline), but it gets the input in a sequential manner. Looking at your paper, for example, they define an online algorithm as (1 Introduction):
An on-line algorithm receives a sequence of requests and must respond
to each request as ...
1
In other words, Djikstra is a form of A* where the heuristic always returns the actual distance.
This is wrong. Dijkstra's is a form of A* where the heuristic is always 0.
Dijkstra's algorithm is essentially the weighted-graph version of a breadth-first search. It simply spreads out from the start node in all directions until it researches the end node. ...
answered Feb 14 at 0:38
BlueRaja - Danny Pflughoeft
1,3781 gold badge9 silver badges14 bronze badges
1
This answers a different question: a cycle is not necessarily simple.
You can use the following dynamic programming solution:
fun dfs(v, start_v, c_pos, visited_vertices):
if c_pos = c.length then
// Used all edges
if v = start_v then
// Returned to the starting vertex
visited_vertices is the answer for the problem
...
1
Welcome to CS.SE.
I propose to list all paths that correspond to the given weight sequence, and keep only the one which are cycles it needed, which is then easy.
A recursive algorithm that appends an edge with weight equal to the first one in the sequence to paths that correspond to the rest of the sequence then makes the job, right?
This leads to the ...
1
Compute all pair to pair distances $D[u,v]$ for $u,v \in V$ using Floyd-Warshall.
For each vertex $s \in V$ construct a graph $H_s$ as follows:
For each edge $e = (u,v)$ check whether $D[s,u] + D[u,v] = D[s,v]$. If the answer is yes the (directed) edge $(u,v)$ belongs to at least one SPT from $s$, and you add $e$ to $H_s$.
This requires time $O(n \cdot m)$ ...
0
I found the answer myself at the end.
Consider this graph and matching (full edge are matched and dashed are not) and suppose we start by exploring the red path from node 1 to 9:
we cannot continue since entering node 7 would create a loop, but during this path we marked node 8 as visited from a non matched edge, and so we will not enter node 8 again ...
3
It looks like you misread or misunderstand the standard set notation "$E'\subseteq E$".
That notation just means $E'$ is a subset of $E$, i.e. every element of $E'$ is also an element of $E$.
We do not speak of "an improper subset", most of the time if not ever.
Why?
Suppose $A$ and $B$ are two sets. $A$ is a subset of $B$ iff every ...
1
Your proposed "broken" solution is actually quite close to the actual solution. You don't need any well known algorithm to do it, but instead you have to notice the following things:
Given that odd == 2, and the two odd vertices are $v,u$ - then we can "fix" them by either connecting them if they are not connected, or by finding another ...
1
I think the issue will be that, if we allow each vertex to be considered twice (once per incoming edge type), then we need some way to remember that if we have already visited one "flavour" of a vertex on the path from the BFS root so far, we must avoid visiting its other flavour further along the same path (since such a path would no longer be ...
1
Here is another reduction from minimum Steiner tree that also shows that your problem is strongly NP-hard.
Let $\langle G, T \rangle$ be an instance of minimum Steiner tree, where $G=(V,E)$ is a graph and $T$ is a set of terminals. Let $w_e$ be the weight of edge $e$ in $G$ and assume that all $w_e$ are positive.
Construct a new graph $G'$ by starting from $...
0
To use dynamic programming, you need to choose the order in which you fill in values for the vertices. The correct order is a topologically sorted order (any other order won't work). So, the two solutions are in some sense equivalent. Any solution is likely to use both components: topological sorting to determine the order to enumerate the vertices, and ...
3
This problem is NP-hard.
Let $S = \{x_1, \dots, x_n\}$ be an instance of partition.
Create a clique $G$ on $n$ nodes $v_1, \dots, v_n$.
Set both the cost and the weight of $v_i$ to $x_i$.
Set $t = \frac{1}{2}\sum_{x_i \in S} x_i$.
If there is a subset $C$ of $S$ such that $2 \sum_{x_i \in C} x_i = \sum_{x_i \in S} x_i$, then the set of vertices $\{v_i \mid ...
1
It is actually finding the number that is NP-complete. The (decision) problem is formally stated as follows:
Vertex cover. Given a graph $G = (V, E)$ and an integer $k$, does there exist a set of at most $k$ vertices $C \subseteq V$ such that every edge has at least one endpoint in $C$?
As you can see, this is precisely your $\tau(G)$.
The other problem is ...
1
Suppose there is an algorithm $A(G,c)$ which runs in time $T(n)$, where $n$ is the number of vertices in $G$, as long as $c$ is the vertex cover number.
Given a graph $G$, run $A(G,0),\ldots,A(G,n)$ in parallel, for $T(n)$ time each. Some of the copies will terminate within $T(n)$, outputting a set. Out of all such outputs which are vertex covers, choose the ...
3
This is probably referring to the communication complexity of the function $f(x,y) = 1$ if $x=y$ and $f(x,y) = 0$ if $x \ne y$. See https://en.wikipedia.org/wiki/Communication_complexity#Example:_%7F'%22%60UNIQ--postMath-00000031-QINU%60%22'%7F for the formulation and a proof of the lower bound.
0
Given a graph $G=(V, E)$, the problem of finding a clique $C$ with $|C| \ge \frac{|V|}{2}$ is a search problem and, as such, is neither in $\mathsf{P}$ nor in $\mathsf{NP}$ since $\mathsf{P} \subseteq \mathsf{NP}$ and $\mathsf{NP}$ only contains decision problems.
Top 50 recent answers are included
