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,179 questions
2
votes
1answer
10 views
Solving the min edge cover using the maximum matching algorithm
To solve an instance of an edge cover, we can use the maximum matching algorithm.
Edge Cover: an edge cover of a graph is a set of edges such that every vertex of the graph is incident to at least ...
0
votes
2answers
31 views
Reducing Graph Reachability to SAT (CNF)
So I came across this problem in my textbook. I was wondering how to develop a reduction from the Graph Reachability problem to SAT (CNF) problem. (i.e. formula is satisfiable iff there exists a path ...
0
votes
0answers
20 views
Does Tarjan algorithm fail for this test case ? references :gfg and Tushar roy's tutorial [on hold]
The test case is : There are 3 vertices 1,2,3 such
edge: source-destination
1-2
1-3
2-3
As dfs proceeds from 1 to 2 and then to 3 . Following are the discovery ...
0
votes
0answers
13 views
What is a polynomial-time algorithm for determining whether two trees, with colored nodes, are isomorphic or not
Provide any polynomial-time algorithm (even a large degree polynomial) which determines whether two rooted colored trees are isomorphic to each-other or not.
For example, consider the following two ...
1
vote
0answers
30 views
Given complete graph, find optimal path with two costs on each edge
We are given complete graph, such that each edge has two costs $a \text{ and } b$. We should find path that passes through each node once and has minimum total cost. Cost of a path is the maximum of ...
1
vote
2answers
27 views
What is the graphic TSP?
I'm not sure if I understand the following definition of the (well-known apparently) Graphic TSP, also known as graph-TSP :
...graph-TSP, that is, the traveling salesman problem where distances ...
4
votes
1answer
98 views
Matching Algorithm - How to maximize matched quantity with unique matching rules?
Given a set $S=\{A,B,\cdots,H\}$. Elements in $S$ can be matched according to the following rules:
$$\begin{aligned}
A\leftrightarrow B\\
C\leftrightarrow D\\
B+C\leftrightarrow F\\
D+A\...
0
votes
0answers
27 views
count all possible paths of length n in an undirected graph with use of dynamic programming [duplicate]
Given is an infinitely large grid graph. Use dynamic programming to calculate the number of possible paths
of a given length n from a given start node, so that fjor every path applies:
a) no vertex ...
1
vote
1answer
28 views
Shortest path in a incomplete graph
I know the Dijkstra algorithm to solve the "single source shortest path" problem in a graph. And I've seen people discuss solutions in a dynamic graph where edge/vertices are subject to change. ...
3
votes
0answers
37 views
Assign weights to the edges in a DAG so that, for all S and T, all paths from S to T have equal weight
I have a DAG, and on each edge, I have a minimum and maximum weight. I would like to assign (or determine it's impossible to assign) exact weights to each edge so that
Each edge's weight is between ...
4
votes
2answers
62 views
Count paths of length $n$ that a player can take
I'm writing a video game, and I'm trying to find an efficient way of calculating this. The goal is to count the number of paths of length $n$ that a character can take, where the character can move ...
1
vote
0answers
56 views
divide and conquer algorithm for finding a 3-colored triangle in an undirected graph with the following properties?
In an undirected Graph G=(V,E) the vertices are colored either red, yellow or green. Furthermore there exist a way to partition the graph into two subsets so that |V1|=|V2| or |V1|=|V2|+1 where the ...
1
vote
1answer
147 views
how to find total paths in a graph which have only one vertex common with a given path
Assume I have a undirected graph $G$ without cycles (i.e., a forest) and I am provided with pair of nodes $a$ and $b$.
How can I find the total number of paths in the graph that do not share any edge ...
2
votes
1answer
22 views
Partitioning a graph with specific constraints
We have an exercise where we need to find the partitions G[V1] and G[V2] of a graph G=(V,E), that fulfill the following constraints. We also know that there exists at least one partition that fulfills ...
4
votes
1answer
28 views
How to construct an ordinary matching from a fractional matching?
Given a graph $G=(V,E)$. A fractional matching, say $f$, assigns every edge $e \in E$ to a fraction $f(e) \in [0,1]$, with the constraint: for $v \in V$, $\sum_{e \ni v}f(e) \leq 1 $.
My question ...
2
votes
1answer
120 views
+50
Algorithm for fewest number of moves with artificial minimum
I asked a question recently, but I need to be able to add an artificial minimum number of steps that can be larger than the Dijkstra minimum.
To summarize, I built an undirected graph with edges ...
3
votes
1answer
64 views
Does a Minimum-Spanning-Tree always give a lower bound for the weight of any Hamiltonian cycle of the graph?
A minimum-spanning-tree (MST) path is always $V-1$ edges and a Hamiltonian Cycle (HC) is always $V$ edges.
Because the HC has an extra edge we could say that in general, the weight of every ...
0
votes
1answer
28 views
How to build tree from graph with specific property
We are given connected undirected graph of $n$ nodes and $m$ edges. On each node one integer(value) from $0$ to $n-1$ is written.
We need to build tree such that for each node $i$, all nodes in the ...
0
votes
1answer
29 views
Finding the maximum disjoint weight in a weighted node graph
I have a graph of nodes that reflect resource allocation. Each node has a weight to reflect this. A well formed graph is disjoint, so there will be no edges, and the weight of the graph is just the ...
2
votes
1answer
15 views
Current value of flow in a network
Confused about a question regarding flow networks.
Question is: Given the network below, what is the current value of flow in this network?
Does the current flow of a network refer to the maximum ...
0
votes
1answer
24 views
Given N vertices and M edges find if two nodes are in the same connected component?
Given a set of $n$ people and $m$ friendship relations between those people (relation is between two persons) we need to suggest a data structure that supports the division of those people into ...
0
votes
0answers
24 views
Graph building time complexity [closed]
Given a list of vertices V = n (n vertices). and a list of edges E = m (m connections).
Is there any way to build an Undirected graph G representation in O(m + n)?
My intuition tells me that we might ...
2
votes
1answer
28 views
Transitive Closure vs Reachability in Graphs
I am facing the most curious situation with [my current information of] transitive closure algorithms. Specifically, is what follows not an algorithm for finding the transitive closure of a graph <...
0
votes
0answers
19 views
What algorithms are there to build a junction tree of a graph?
A junction tree of a graph is a tree that represents the graph, so that certain information about the graph is encoded in the tree.
What algorithms are there to build a junction tree of a graph?
4
votes
1answer
29 views
Graph ordering with smallest max vertex “discrepancy”
Consider an undirected graph $G=(V,E)$ and a bijective function $f:V \rightarrow [|V|]$ which orders the vertices by mapping them onto the first $|V|$ natural numbers.
Define the cost of an ordering ...
2
votes
1answer
28 views
What algorithm will tell us how to divide-up a round robin tournament into rounds?
We are designing a tournament for a game such as soccer (football) or chess. The tournament is "round robin." By "round robin," we mean that every team gets to play against each other team exactly ...
0
votes
0answers
21 views
Single source shortest paths with even path [duplicate]
Given directed graph with non negative weights and vertex s.
I need an algorithm that finds shortest paths from s to all vertices and the paths have to be even.
1
vote
1answer
34 views
What are examples of applications of the tree decomposition of a graph? [closed]
I am looking for specific applications of the tree decomposition (of a graph), because I want to motivate its existence. What are examples of problems that are more easily solvable using the junction ...
1
vote
1answer
52 views
Maximum weight vertex-disjoint paths
I have a complete (every vertex is connected by an edge to every other vertex) undirected positively weighted graph. I want to find vertex-disjoint paths in the graph whose total weight is as large ...
0
votes
0answers
64 views
Shortest path for vehicle routing problem with alternative locations
I'm currently developing an algorithm that solves the vehicle routing problem with time windows and the possibility for clients to be delivered to multiple locations.
Right now, I'm trying to find ...
1
vote
0answers
34 views
Make maze connected removing minimal number of obstacles
Input consists of two numbers $n$ (number of rows) and $m$ (number of columns) with the maze consisting of $2\cdot n + 1$ rows, where each row consists of $2\cdot m + 1$ symbols: '+', '-', '|', '.'
...
1
vote
0answers
19 views
Directed weighted multigraph isomorphism algorithms
Are there known algorithms for the isomorphism problem for directed weighted multigraphs? If not, could one be created simply by adapting existing algorithms for graphs or digraphs, or is it entirely ...
1
vote
1answer
37 views
Finding a cycle in a graph with the biggest value (the sum of all edges)
I am trying to solve this problem: we have an oriented, weighted graph and we have to find a cycle with the biggest weight. Weight of a cycle is the sum of all edges forming the weight. The preferred ...
3
votes
1answer
46 views
Cannibals missionaries problem - solving usings graphs
I am trying to solve the cannibals - missionaries problem; we have the number of cannibals, the number of missionaries and the position of the boat. We are trying to transfer all of them to the other ...
2
votes
3answers
51 views
Shortest path between any origin to any destination through some way stations
How can one find the shortest path between any one of the origins to any one of the destinations through a number of way stations on the way using Dijkstra algorithm?
You can visit those way stations ...
0
votes
0answers
33 views
What is the most efficient way to solve a workshop scheduling problem?
I am trying to design an algorithm to solve a workshop scheduling problem.
The problem is as follows:
I have to schedule a workshop consisting of a finite number of time slots, and a finite number of ...
2
votes
1answer
43 views
Existence of path under weight and value budgets
Consider the following problem:
Input: An undirected graph $G = (V, E)$, each edge has a non-negative weight $w_i$ and a non-negative value $v_i$. There are two vertices to represent start point $s$...
0
votes
0answers
9 views
Online bipartite matching problem for task assignment
I have $n$ drivers, each one has a balance (in Us dollars), availability status (true if he is not working already) and number of accomplished tasks in the current ...
1
vote
0answers
14 views
Understanding proof of upper bound on complexity of recursive computation of graph chromatic polynomial
This question is about section 2.3 of Wilf's ``Algorithms and Complexity''
https://www.math.upenn.edu/~wilf/AlgoComp.pdf
in which he analyses the complexity of a recursive computation of the ...
2
votes
0answers
39 views
Optimizing De Boor's algorithm
According to De Boor's algorithm, a B-Spline basis function can be evaluated using the formula:
$$ B_{i,0} =
\left\{ \begin{array}{ll}
1 & \mbox{if } t_i \le x < t_{i+1} \\
0 &...
3
votes
2answers
42 views
Graphs of maximum degree three
I'm learning an algorithm for graphs of maximum degree three.
My question is: should the graph of that type have at least one vertex with degree three.
For example if the maximum degree of some ...
1
vote
0answers
10 views
complexity of computing fractional edge-chromatic number of an edge-weighted graph
Let $(G,w)$ be an edge-weighted graph, where the weights $w(e)$ are assumed to be rational. My question is: What is the complexity of computing $\chi'_f(G,w)$, the fractional edge-chromatic number of ...
1
vote
1answer
43 views
Minimum distance of nodes from a set of two nodes
In an unweighted tree, suppose that we want to delete (or mark) any node which is closer to node $v$ than node $w$ ($dist(x,v) < dist(x,w)$). The solution that comes to my mind is running two BFS, ...
0
votes
0answers
19 views
UnionFind different version performance
I am studying the Union Find data structure using this material written by Sedgwick et al.
I am specifically interested in the versions they call QuickFindUF, <...
0
votes
0answers
36 views
Is it NP-complete to test if a graph contains $t$ $k$-cliques?
Let $(G,t,k)$ - a graph with $t$ cliques with $k$ vertices (there are $t$ cliques of size $k$ in graph $G$), for $t,k > 100$. How to prove that $(G,t,k)$ is NP-complete?
It is obvious that it is ...
3
votes
2answers
61 views
Minimize number of DFS searches in a graph
I got a weird homework question about graph.
A helicopter is going to land on an island to check the n houses after an earthquake. Some of the two-way roads connecting the houses are destroyed ...
1
vote
0answers
20 views
How to Track Connected Components in a Graph when Deleting Nodes
Suppose you have a graph G, and you want to support the following operations:
addNode(Node n)
addEdge(Node n1, Node n2)
...
0
votes
2answers
21 views
Spanning trees on disconnected graphs
Can anyone please help me out with my query: can disconnected graphs have minimum spanning trees?
0
votes
0answers
26 views
Is retrospective inference NP-hard?
Here is a minimal working example of the question:
Consider a network with nodes arranged in a pyramid: $1$ node in the first row, $1+d$ nodes in the second, $1+2d$ nodes in the third, and so on, ...
1
vote
1answer
28 views
Determining the number of walks between two vertices in a graph
Given a graph G and a set of vertices $(v_1, v_2)$.
How can you determine whether there is $\textit{one}$ unique walk between $v_1$ and $v_2$?
