Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [graphs]

Questions about graphs, discrete structures of nodes which are connected by edges. Popular flavors are trees and networks with edge capacity.

2
votes
1answer
39 views

Algorithm to find sets of vertices connected to at most one incoming and one outgoing vertex outside the set

I have a directed graph with vertices $V$, and I need to find a strict subset $U$ of its vertices such that: $U$ contains at least two vertices, and $U \neq V$ There is at most one vertex in $V \...
1
vote
1answer
35 views

Generating a random minimum spanning tree

I am tring to find the simplest method of generating a random minimum spanning tree. My intention is to randomly generate a Level in a game where there are n amount of fixed sized rooms existing on a ...
1
vote
1answer
33 views

Polynomial time algorithm - Matching pairs of vertices

Let T be a tree with root r and S a set with an even number of vertices of T. Design a polynomial time algorithm that finds |S|/2 simple and disjoint paths in edges matching pairs of vertices in S. ...
1
vote
0answers
26 views

Solving a pursuit-evasion game

Let's say we have a simple connected and undirected graph $G(V,E)$. The game is played with two players. For each game, player A starts at a node $t$, and player B at a node $v$. There is also a node $...
1
vote
1answer
56 views

Word ladder problem for words with different length

Is there some one who know any algorithm for word ladder problem with words of different length? Actually we have some strings with same length and some strings with one length longer but not from ...
1
vote
1answer
44 views

Proving correctness of inefficient algorithm - Path between two vertices

Consider the following inefficient algorithm that decides if there is a path between two vertices s and t of a directed graph G. Show that the algorithm is correct. In addition, analyze its complexity ...
0
votes
0answers
30 views

Counting chords intersections in a circle

The problem is: Given 2n distinct endpoints of n chords on the unit circle, count the number of intersections between chords (if k chords intersect at one point, that point counts as $\binom{n}{2}$ ...
0
votes
2answers
36 views

“Process functions” in iterative and recursive depth-first search

I was reading The Algorithm Design Manual by Steven Skiena, and I noticed his use of "process functions" in depth-first search and breadth-first search. Consider the following pseudocode for depth-...
0
votes
0answers
27 views

Practical computation time, counting spanning trees and selecting spanning trees uniformly at random

I am doing a project in applied math, which involves counting spanning trees and selecting spanning trees uniformly at random for near-maximal planar graphs with ~430 vertices, as part of a larger ...
4
votes
3answers
254 views

Hard connected instances for Weisfeiler-Lehman test of isomorphism

There are instances when WL algorithm fails. For example graphs G1 and G2 below have the same coloring after WL-1 algorithm. However, one of these graphs is disconnected. So what are the instances ...
1
vote
0answers
14 views

Relation between deficiency and color class parity of graphs

Let $G$ be a graph with total vertices $|V(G)|$. Let the maximum degree of the graph be $\Delta$. Let us assume the graph is total colourable( no adjacent vertices, adjacent edges and an edge and its ...
2
votes
1answer
43 views

Given a set of intervals on the real line, find a minimum set of points that “cover” all the intervals

I've been trying to find an efficient way to solve the problem of finding a minimum (not minimal) set of time points that cover a given family of intervals on the real line, that is, for each interval ...
2
votes
0answers
33 views

Method to calculate score in a go game

I'm currently programming a go game, and I'm struggling with some aspect of the game, especially how to handle the end game, how to count points and how to detect dead stones ? I thought of doing a ...
1
vote
2answers
42 views

Two Problems in understanding the algorithm for computing shortest paths in undirected graphs with possibly negative edge weights

Section 2 of this Lecture Note: Shortest Path Algorithms Luis Goddyn, Math 408 describes an algorithm using Edmonds' Minimum Weight Perfect Matching Algorithm to solve the shortest path problem for ...
0
votes
1answer
33 views

Graph Edit Distance

Source: K. Riesen, Structural Pattern Recognition with Graph Edit Distance, Advances in Computer Vision and Pattern Recognition. Link: https://www.springer.com/cda/content/document/...
0
votes
0answers
10 views

How can we implement efficiently a maximum set coverage arc of fixed cardinality?

I am working on solving the following problem and implement the solution in C++. Let us assume that we have an oriented weighted graph $G = (V, A, w)$ and $P$ a set of persons. We receive a number ...
5
votes
1answer
56 views

Least number of guesses needed to determine all unknown subsets of a set

Say I have a set $\mathbb{S}=\{1,2,...,n\}$. I have an adversary who breaks up $\mathbb{S}$ into $k$ unknown and disjoint subsets. Denote this new set $\mathbb{A}$. I can guess any combination $s$ and ...
1
vote
1answer
38 views

Find the minimum edge size, L, that would allow the construction of a tree whose edges connect all given 2-d points, but no edge exceeds length L

Given a set of points in the 2-d plane, find the minimum edge size, L, that would allow the construction of a tree whose edges connect all given points, but no edge exceeds length L. Here is an ...
0
votes
1answer
62 views

Create a binary search tree from a sorted array: Space complexity reasoning

Here is the Python code. The solution is fairly common and is seen in most textbooks like 'Cracking the Coding Interview' and 'Element of Programming Interviews'. ...
3
votes
1answer
40 views

K Perfect Subgraph Algorithm

I have a problem that goes as follows: Problem. Suppose we have undirected graph $G$. We denote a $k$-perfect graph as a graph such that $\forall v \in G, degree(v) = k$. Present an algorithm that ...
0
votes
2answers
66 views

Time Complexity and graphs

I'm learning graphs these days and need to clear few doubts- Can I determine weather 5 points in two dimensions whose X and Y coordinates are given lie on the same straight line in O(1). What is the ...
2
votes
2answers
132 views

Find shortest path that goes through at least 5 red edges

Let $G=(V,E)$ be a directed graph, $\omega : E \rightarrow R$ a weight function, and $s,t \in V$ a pair of different nodes. It's given that $G$ doesn't have a negative cycle. Moreover, 10 of its edges ...
4
votes
2answers
134 views

What is the point of traversing a binary tree in preoder, inorder or postorder?

Why would you want to traverse a binary tree in preoder, inorder or postorder? Why not use an order like breadth-first search for all graphs?
2
votes
1answer
107 views

Finding the longest path in an undirected node-weighted tree

I have a tree where each node is assigned a weight (a real number that can be positive or negative). I need an algorithm to find a simple path of maximum total weight (that is, a simple path where the ...
0
votes
0answers
15 views

How would I optimize a tree-like graph with a significant number of redundant nodes?

Recently, I was looking at the underlying data/implementation of a survey application created using a RPA tool. As a user progresses through the survey, the "decisions" reveal a predominantly tree-...
1
vote
1answer
121 views

How to reduce 3-COLOR to 42-COLOR?

The requirement is that two adjacent vertices have different colors, and max. 42 colors. I show that $ \text{42-COLOR} $ is in NP and then I must reduce it from $ \text{3-COLOR} $. Here it becomes ...
1
vote
0answers
23 views

directed edges in an undirected graph [duplicate]

Undirected graph is given which has M edges and N vertices we have to convert every edge from u−v to u→v or v→u such that the total outdegree of every vertex is even. For example, consider a graph ...
1
vote
1answer
31 views

Every vertex cover is a dominating set

Suppose $G$ is a connected graph and $S$ is a vertex cover. Prove that $S$ is also a dominating set. Can I get some help with proving this? I know that a dominating set in an undirected graph $G=(V,E)...
1
vote
1answer
47 views

Distinct Minimum Weight Spanning Trees

I am trying to find the total number of distinct minimum weight spanning trees(MWST) in a simple, undirected, unlabeled and weighted graph but I am confused whether should I have to consider ...
-2
votes
1answer
117 views

Please indicate whether each of the following statements is TRUE or FALSE and provide a brief justification

I provided my answers in the "answer your own question" bit. I have applied the same logic for my answers to a&b and c&c which seem to be essentially the same questions. Am I right though? a)...
1
vote
0answers
9 views

Decremental connectivity on general graphs

I'm looking for an efficient solution to the problem of tracking the number of connected components in a general graph under edge deletions. General connectivity algorithms like that from Holm, ...
0
votes
1answer
18 views

Do these answers work even when we change the values?

So I know that these are both true, but if I change the values would they still be true? Do these statements hold for any value? A) Suppose f is a flow of value 50 from s to t in a flow network G. ...
1
vote
3answers
53 views

Is this definition of a “complete graph” correct?

Is it correct to say that: "A complete graph is a graph in which each vertex is connected to all other vertices in the graph" That's how I always thought about it, the official definition is ...
2
votes
1answer
25 views

Mean geodesic distance between two points in Delaunay Graph

If I have a Delaunay Graph, what is the mean geodesic distance between two randomly chosen nodes. I know that in a small world network, it is in O(log(N)), with N being the number of nodes. Thank you!...
2
votes
1answer
556 views

Direct edges of undirected graph so that all indegrees are even

Undirected graph is given which has M edges and N vertices we have to convert every edge from $u-v$ to $u\to v$ or $v\to u$ such that the total indegree of every vertex is even. For example, consider ...
3
votes
3answers
114 views

Undirected graph with exponential number of simple cycles

Hey I am new to graph theory and this question has me stuck for hours. What is an example of undirected graph with n nodes where the number of simple cycles is exponential in n. I was looking at ...
1
vote
1answer
36 views

Graph theory: determining maximum number of edges

Based on the question below, can someone please explain to me the reasoning behind why the maximum number of edge is 5/2|V|? I don't find the particular reasoning in the solution to be that helpful ...
0
votes
0answers
34 views

Finding shortest cycle in graph with positive weights

Given a graph G, with all positive weights, find the shortest cycle length in O(V^3) My idea is, negate al the edges, apply floyd-warshall algorithm and then for all $i$, find the largest $M[i][i]$ ...
3
votes
1answer
45 views

Strongly connected orientations of undirected graphs

I'm trying to prove the following. There exists a strongly connected orientation of a connected, undirected graph $G$ if, and only if, $G$ has no bridge. (An orientation of an undirected ...
0
votes
2answers
51 views

Shortest distance from multiple points to one point

I am looking for an algorithm to find the shortest distance from multiple nodes to one end node. For example let $v_1,v_2,\dots,v_r$ be the nodes on a graph with distance $d_1,d_2,\dots,d_r$ to the ...
1
vote
1answer
35 views

What happens if I replace $<$ with $\le$ in Dijkstra's algorithm?

The following is Dijkstra's algorithm for finding the shortest path in a graph. I know something wrong happens if I replace d[u] + weight(u,v) < d[v] with ...
0
votes
0answers
57 views

Intuition behind Floyd-Warshall being faster

I know the Floyd-Warshall, and I also clearly understand the proof of running time of $O(V^3)$ of F-W algorithm. However, consider this algorithm: Let $dp[i][j][n]$ denote the shortest path from $...
3
votes
2answers
64 views

Calculate the number of cycles of a Cactus graph?

Considering a cactus graph $G = (V, E)$, defined as: A graph is a cactus if every edge is part of at most one cycle. There is a way to calculate the number of cycles in this graph given only $n= |...
1
vote
1answer
19 views

Tracing a polynomial algorithm for the problem of maximum-weight independent set

It should be a very easy question, but I am a little bit confused. According to party optimization post, the Maximum-weight Independent Set for trees can be found in the poly-nominal time using ...
0
votes
2answers
44 views

Finding shortest path between two nodes with a set of forbidden nodes

I have undirected and unweighted graph, in which I would like to find the shortest path between two entered nodes. There is also a set of forbidden nodes. How to find the shortest path, if I am ...
21
votes
5answers
3k views

Do any two spanning trees of a simple graph always have some common edges?

I tried few cases and found any two spanning tree of a simple graph has some common edges. I mean I couldn't find any counter example so far. But I couldn't prove or disprove this either. How to ...
0
votes
1answer
42 views

Proving that a spanning tree of graph is not a minimum

Let $G$ be an undirected and connected graph. Let $T$ be a spanning tree of $G$ with edges weights: $w_1 \le, w_2 \le ... \le w_{n-1}$ which are responing to the edges. $e_1,e_2,...,e_{n-1}$. Now I ...
0
votes
1answer
36 views

More efficient maximum bipartite matching

I've been looking into weighted matching in bipartite graphs and am currently looking at maximum matchings in weighted bipartite graphs. As I've been reading and poking around at different books and ...
1
vote
2answers
27 views

Minimum number of components in graph

Minimum number of components in graph where we have 69 vertices and 43 edges. I think the best way is to create a path? One path and the rest would be isolated components. Since in path we use only ...