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.

0
votes
0answers
4 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
30 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
12 views

Does Tarjan algorithm fail for this test case ? references :gfg and Tushar roy's tutorial

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
27 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
55 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
118 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
63 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
14 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
27 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
41 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$?