Questions tagged [graphs]

Questions about graphs, discrete structures of nodes which are connected by edges, including trees and graphs with weighted edges.

Filter by
Sorted by
Tagged with
0
votes
0answers
20 views

Score and bound in Goemans-Williamson algorithm

I am trying to have a deeper understanding of the following implementation of the Goemans-Williamson algorithm for solving the maxcut problem. ...
4
votes
2answers
63 views

How to match two point sets to minimize total distance?

Let's say we have two sets $X = \{x_1, \ldots, x_n\} \subset \mathbb R^d$, $Y =\{y_1,\ldots, y_n\} \subset \mathbb R^d$, how can we find a permutation $\pi$ such that $$D = \sum_{i=1}^n d(x_i, y_{\pi(...
3
votes
1answer
99 views

Winning move in graph based strategy game

I'm prototyping a deterministic Risk like game. A player can move units from one node to a connected node if he has more than 1 unit the in origin node (must leave 1 unit behind). The player wins if ...
6
votes
5answers
2k views

Example of a graph with negative weighed edges in which Dijkstra's algorithm does work

I was asked to give an example of a graph that has edges with negative weight, but Dijkstra's algorithm will still give us the correct output. It was part of a prove/disprove question. The claim was.. ...
1
vote
1answer
23 views

Complexity of checking graph separation

Let $G=(V,E)$ be an undirected graph and $A,B,C\subset V$ disjoint subsets of $V$. I want to check whether or not $A$ and $B$ are separated by $C$ (i.e. every path from $A$ to $B$ passes through $C$). ...
4
votes
2answers
101 views

Why do basic graph algorithms (BFS, DFS, Prim, Kruskal) have a similar structure?

This is my first post on CS Stack Exchange. For some time, I have been studying basic graph algorithms, mainly BFS, DFS, minimum spanning trees and their basic algorithms (Kruskal and Prim). One thing ...
3
votes
1answer
200 views

Disconnected bipartite graph

I was searching whether a bipartite graph can have a vertex with 0 degree. I found this, but the answer there says it is possible. Wouldn't that make a graph tripartite? Also, if a vertex with zero ...
1
vote
2answers
68 views

Show that for a singly-connected graph the number of edges $E$ must be equal to the number of vertices minus $1$, $E=V-1$

I am reading "Bayesian Reasoning and Machine Learning By David Barber". I am not completely sure how to do question 19 on page 23: Show that for a connected graph that is singly-connected, ...
2
votes
2answers
42 views

Algorithm that will find the minimum number of steps to get from state $j$ to state $i$

Consider an adjacency matrix $A$ with elements $[A]_{ij}=1$ if one can reach state $i$ from state $j$ in one timestep, and $0$ otherwise. The matrix $[A^k]_{ij}$ represents the number of paths that ...
2
votes
1answer
165 views

Topological sort and finding longest path in DAG to solve a stacking boxes variation (no rotation)

Given n elements (boxes) I have to output the max number of boxes that can fit one into another. Each box has width (x), height (y) and depth (z). One box j can hold another box k if: ...
0
votes
3answers
71 views

O(m) time algorithm to check for a strongly connected graph

Given a directed graph G=(V,E) how can I check to see if it is strongly connected i.e. every vertex is reachable from every other vertex. what's a good algorithm to check for this that runs in O(m) ...
1
vote
0answers
23 views

Maximum number of edges with k components

Given $N$ vertices and $K$ components what is the maximum number of edges that may exists ? I just got gut instinct that it will be maximum if we take one set with $k-1$ vertices and this will have no ...
3
votes
0answers
41 views

Finding a minimal colored graph containing all given subgraphs

I suspect this is a standard problem, but I was unable to find any literature on it -- my question is, what is the canonical formulation (and ideally solution) to the following: Given a set $S$ of $K$...
2
votes
0answers
27 views

Best grid/lines to map a group of points

The data I have is a group of points with their position (x,y) known: It is known that all these red dots are situated exactly on the lines which form a grid system like following: My object is to ...
2
votes
1answer
49 views

Coming up with an adversary strategy for a clique of maximum size

I’m having trouble coming up with a good adversary strategy for this problem: Input: a graph G Output: the maximum size of any clique in G Where the algorithm asks each time, “are vertices x and y ...
1
vote
0answers
11 views

Distributed Graph Consensus to fit a distribution?

$G$ is a strongly connected graph with nodes $V$ and edges $E$. Each node $v_i$ receives a sample $x_i$ from a Gaussian $\mathcal{N}(\mu,\sigma^2)$ with unknown mean and variance. The objective is for ...
0
votes
2answers
165 views

Time Complexity for brute force algorithm finding cliques of size k in a graph, in terms of n m and k

I currently have an algorithm that uses brute force/exhaustive search to find all of the cliques of size exactly k in a graph G. My algorithm is as follows: Generate all subgraphs of size k, and check ...
0
votes
0answers
40 views

Graph minimal cycles

Given a graph G, we say C a cycle of G such that however we take two nodes a and b of C, there is NOT a path between a and b in G\edges(C) (that is the graph G less the edges of C). Is C a minimal ...
0
votes
0answers
20 views

Visit each node in a circular graph with most distance

A simple graph is shown below with 10 nodes. Each node is labeled after a letter in the alphabet. This is basically a circle (J connects to A). ...
0
votes
0answers
36 views

A relaxation-free variant of Dijkstra's shortest path algorithm

I have come up with a relaxation-free variant of Dijkstra's shortest path algorithm, and I would like to see if it's correct. Here is the pseudocode for finding the shortest distance from a node $\...
0
votes
1answer
19 views

how do i remove nodes with their children but keep ones that are already connected?

suppose you have graph G and you want to remove node n and n and all of his children but keep the ones that are connected to other nodes if i want to delete A it will delete C but not D becase its ...
2
votes
2answers
81 views

Given DAG $G(V,E)$, find $\forall v \in V$ the sum of the weights of vertices that are reachable from the $v$

Given a DAG $G=(V,E)$ and a weights function on the vertices $w:V \to \mathbb{R}$, suggest an algorithm that computes for every $v \in V$ the sum of the weights of vertices that are reachable from it. ...
1
vote
0answers
9 views

Methods to interpolate between 2 topologically identical 3D meshes

I have 2 3D surface meshes. These meshes have vertex-correspondence and have the same topology (same edges and triangles connecting the vertices). However, the vertex positions (3d coordinates) are ...
0
votes
0answers
32 views

Finding the shortest distance between two nodes given multiple graphs

Assume that we have a set of nodes and multiple graphs with different edge values for the same set of nodes. As an example, there are 4 nodes A, ...
0
votes
1answer
110 views

An "easy" graph problem I can't solve

The question is: A given graph is given with only weights 1 or 2 on its arcs. (I.e. each arc has a weight of 1 or a weight of 2) And a origin vertex s. Write an efficient algorithm that finds the ...
3
votes
0answers
31 views

Shortest path which passes through a subset of vertices in an unweighted directed graph [duplicate]

Given an unweighted directed graph $G=(V, E)$, two vertices $s,t \in V$ and a subset of vertices $U \subseteq V$, suggest an algorithm which concludes if there exists a shortest path from $s$ to $t$ ...
0
votes
0answers
16 views

How to convert SDF to CSDF graph?

A sample example of Synchronous Data Flow (SDF) graph (from here): How to convert it to Cyclo-Static Synchronous Data Flow (CSDF) graph?
0
votes
0answers
21 views

How to close an open polygonal chain such that the resulting enclosed area includes polygon B and excludes polygon C?

I have an algorithmic question for you: Given: 3D triangle surface mesh, open polygonal chain A, closed polygon B, closed polygon C, all on the mesh. Wanted: A line that closes A such that B lies ...
0
votes
0answers
30 views

How to close an open polygonal chain in clock- or counterclockwise direction?

I have an algorithmic problem that I am hoping someone can help me out with: Given: 3D triangle surface mesh, an open polygonal chain (blue). Wanted: A line that closes the blue line in clockwise ...
3
votes
0answers
114 views

Seemingly simple path finding problem, but graph with travelling salesman or shortest path does not work

I am looking for an algorithm to a problem that I encountered when working with 3D modeling: On a 3D triangle surface mesh, I have multiple lines, some of them are open, some are closed. The are on ...
2
votes
0answers
30 views

Given a vertex in a digraph, is there a standard term for (the vertices reachable from it) union (the vertices reaching it)?

Question in title. Looking for whether there is a term that is, if not widely understood, at least citeable to a source. This is equivalent to asking for the set of nodes that are comparable to the ...
0
votes
1answer
31 views

If in a given text the frequency of the letter A is 0.5, then the number of bits encoding in the Hoffman code for the text is 1

Studying for my finals. I saw the following question: Prove or disprove: If in a given text the frequency of the letter A is 0.5, then the number of bits encoding in the Hoffman code for the text is ...
1
vote
1answer
51 views

In every DFS run on $G$, in every step of DFS, the $G_{\pi}$ is a forest

Studying for my finals. So I'm reading the "Introduction to Algorithms (Third Edition)" book. In the DFS section there is the following section: Depth-first search yields valuable ...
2
votes
1answer
41 views

Is doing BFS over transitive reduction of a directed acyclic graph equivalent to topological ordering of that graph?

I have a directed acyclic graph. Where each node is a task and each edge denotes a dependency. I want a method to effectively parallelize these tasks. One way would be to topological sort them based ...
0
votes
2answers
105 views

Reduction between CLIQUE to SUBSET SUM

I have a question from a test that I failed to pass, I failed to do the question. The question is about the reduction between Clique and Subset Sum. I tried to find an explanation for this on the ...
0
votes
2answers
175 views

edge-coloring and vertex-coloring reduction problem

I study complexity and computation independently. I have a problem that I can not solve. That's the problem: Edge-Coloring problem, we get as input graph G = (V, E) and natural number k and ask "...
0
votes
2answers
25 views

Adding Links to Reduce Diameter

Given an unweighted graph $G$, the problem is to add links to the graph with total minimum cost such that the diameter of the graph becomes at most a constant $k$? The cost of adding a link $(u,v)$ is ...
0
votes
1answer
40 views

Reduction from the Clique problem to the Odd Clique problem

I have a question that is not clear to me, and I have not been able to answer it from a test I had. This is the question: Let's look at the problem $Oclique$ , In it we get a graph $G = (V,E)$ , And ...
1
vote
1answer
56 views

For any direct graph $G(V,E)$, there is always an iteration of DFS algorithm on $G$ so the result does not have any cross trees

I suspect that it is not true but I came across with the following statement: For any direct graph $G(V,E)$, there is always an iteration of DFS algorithm on $G$ so the result does not have any cross ...
2
votes
2answers
36 views

There exists some number $x$ so in any run of BFS from vertex $w$, so the distance from $u$ to $v$ in BFS tree is always $x$

Studying for my finals and stuck on the following question: Prove or disprove: Given an undirected and connected graph $G=(V,E)$ and three different vertices $u,v,w\in V$ then there exists some ...
1
vote
1answer
65 views

edge-coloring reduction problem

I study complexity and computation independently. I have a problem that I can not solve. That's the problem: Edge-Coloring problem, we get as input graph G = (V, E) and natural number k and ask "...
2
votes
2answers
109 views

Efficiently check if removing an edge splits a strongly connected component

I have a strongly connected component (SCC) of $n$ vertices. Let $n_1n_2$ be an edge between two vertices $n_1$ and $n_2$ in this SCC. Is there an efficient algorithm to check if removing the edge $...
0
votes
0answers
13 views

Maximal independent set, with non-additive weights

Consider the following variant of the problem of finding the maximal weighted independent set in a vertex-weighted graph $G=G(V,E)$. Weights $w_v$ for $v\in V$ need not be positive reals; say they lie ...
1
vote
1answer
28 views

Given graph $G=(V,E)$ and weight function $w\,:\,E\to\mathbb{N}$, function $f(G,w)$ finds the heaviest clique in the graph, prove $L(M)=CLIQUE$

Given graph $G=(V,E)$ and weight function $w\,:\,E\to\mathbb{N}$, function $f(G,w)$ finds the heaviest clique in the graph, when the sum of a clique is the sum of the weights on all of the edges. I ...
0
votes
0answers
15 views

Mechanism of Howard's algorithm

How does Howard's algorithm avoids re-mapping of the non-critical nodes ?
1
vote
0answers
39 views

Puzzled by this interview problem of scheduling a computation graph on a single-processor under a memory constraint

I recently went through a interview session for a SWE/CS role at a well known company. It wasn't specifically a "coding-round" but was titled a "domain interview" session, so I ...
2
votes
1answer
39 views

Finding an optimal solution in a tile painting game

The Problem Find the shortest sequence of moves that makes up the optimal solution of a level. If there is more than one optimal solution, just find one of them. Game Rules The game level is made up ...
1
vote
0answers
30 views

Modified Kruskal's Algorithm

I have a connected graph, each vertex has a cost. I want to slice the graph into as many components as possible, but each component should have a cost (sum of costs of vertices) at least C. I think it ...
0
votes
1answer
229 views

When would it be optimal to use an Edge List as opposed to an Adjacency List / Matrix when representing a graph?

This seems to be my first ever question :) Given that adjacency lists store all the necessary information with regards to the endpoints of an edge, we could even store a weight alongside that. I don't ...
0
votes
0answers
14 views

Precondition of all-pairs shortest-paths algorithm

In Retiming Synchronous Circuitry , why put a negative sign to d(u) in step 1 ? Why there is no subtraction operation for W(u, v) in step 3?

1
3 4
5
6 7
87