Questions tagged [graphs]

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

Filter by
Sorted by
Tagged with
2
votes
2answers
50 views

Graph search or shortest path algorithm for graph with multiple “goals”?

I did a project in a class using A* search to solve an 8-puzzle. But what about a puzzle with multiple ‘solved’ states? For example, and 8 puzzle with some repeated tiles. I’m not sure whether ...
0
votes
1answer
42 views

Algorithm to figure our deps in a graph that can resolve deps from cache (dictionary) of walked paths

I have a graph like this that starts from one top node and has cycles: I need to write an algorithm to figure if node1 depends on ...
0
votes
1answer
52 views

Distribution of resources from providers to maximum number of receivers

Consider there is a city with $n$ residents who are in need of internet and there are $m$ internet providers in the city. Here in the city every resident needs internet and every resident knows what ...
6
votes
2answers
185 views

Odd cycle transversal and linear programming

Suppose we have a graph $G$ with $n$ vertices. Suppose LP is a linear programming problem where there is a variable for each vertex of $G$, each variable can take value $≥0$, for each odd cycle of $G$ ...
2
votes
1answer
69 views

Finding all partitions of a grid into k connected components

I am working on floor planing on small orthogonal grids. I want to partition a given $m \times n$ grid into $k$ (where $k \leq nm$, but usually $k \ll nm$) connected components in all possible ways so ...
3
votes
1answer
67 views

Algorithm to compute average length of a simple path

Given a connected graph and two nodes s and t, there can be many different simple paths (without cycles) from s to t. Is there an efficient algorithm to find the average length of these paths?
3
votes
0answers
105 views

Time taken by virus to reach all nodes

Given a connected graph, with weighted edges, a virus starts from a given node. It takes x seconds for the virus to travel from a node to one of its neighbours where x is directly proportional to the ...
0
votes
0answers
15 views

Is there a way to solve the optimal branching / arborescence problem with path-dependent weights?

The optimal branching problem (solved by Edmond's algo or Tarjan's algo) finds the spanning arborescence for a particular graph. [0] I'm looking for a formulation of the problem that allows for path-...
6
votes
2answers
161 views

Spanning tree in a graph of intersecting sets

Consider $n$ sets, $X_i$, each having $n$ elements or fewer, drawn among a set of at most $m \gt n$ elements. In other words $$\forall i \in [1 \ldots n],~|X_i| \le n~\wedge~\left|\bigcup_{i=1}^n X_i\...
1
vote
1answer
40 views

In the dataflow programming paradigm programs are modeled as directed graphs. Are the edges of the graph variables? And are the vertexes functions?

As I understand it in dataflow programming, programs are structured as directed graphs, an example of which is below Is it true to say that the arrows (or edges) represent the variables within a ...
0
votes
1answer
66 views

algorithm to find shortest path connecting EVERY node

I have received a problem to solve and I am not sure what algorithm to use. TLDR; Find the shortest path to get to every node in a undirected graph The problem states that one must visit every ...
2
votes
1answer
71 views

Calculating the structural integrity of a pixel grid

Preface So this is a question that came from an idea for a game. This game is voxel-based, and I am interested in calculating structural integrity, with some blocks that break after a limit has been ...
0
votes
2answers
66 views

Confusion in Reduction of Hamiltonian-Path to Hamiltonian-Cycle

The following is an excerpt from a material on NP-Theory: "Let G be an undirected graph and let s and t be vertices in G. A Hamiltonian path in G is a path from s to t using edges of G, on which ...
0
votes
0answers
19 views

Dinamic programming relationships in the all-pairs shortest paths problem

CLRS includes two dynamic programming algorithms for solving the same problem: all-pairs shortest paths. The kernels of these algorithms (side-by-side) look almost identical, except that they seem to ...
0
votes
1answer
24 views

The definition of a graph's transitive reduction

I want to determine the transitive reduction of this graph: as of now, I only found the first step of doing this: represent the transitive closure of the graph as an adjacency relation, so this is ...
0
votes
0answers
8 views

Community detections in networks using more than one factor?

all community detection algorithms in major python packages are using only edges & edge weights. Is there any algorithm that uses multiple attributes of nodes to detect communities? For ex, in ...
1
vote
1answer
36 views

Is there such a problem as b-Matching with different b values?

Consider a bipartite Garph $G=(L \cup R, E)$. Naturally, a b-Matching problem is to find a set of edges $M \subset E$, such that each node in $L$ and $R$ are adjuscent to maximum $b$ neighbors, and a ...
-1
votes
1answer
51 views

Algorithm for display nodes of a particular node based on in-degree and out-degree

Suppose we have following directed graph. When I click on say node $e$, it should make in-degree and out-degree of node $e$ and connected nodes red. As shown in Resulting Graph. My purpose is, when I ...
0
votes
0answers
22 views

Analyzing a counting triangles streaming algorithm which uses $\ell_0$ sampling

I'm trying to analyze the following streaming algorithm for counting triangles (see below). It supposedly works also for dynamic graphs (i.e. "turnstile model", where edge deletions are ...
4
votes
1answer
68 views

First-time and second-time seen edges in DFS on undirected graphs

Assume an undirected graph and a DFS traversal on it. I am interested in the DFS tree which encodes the discoverer/discovered (parent/child) relationships of the traversal. Just to make sure we are on ...
0
votes
1answer
76 views

Finding the connected subgraph of a given size with maximum number of edges, that includes a given vertex

Consider an undirected graph $G = [V,E]$. Let $V$ be the set of vertices: $V = \{v_1,..,v_n\}$ and $E$ be the set of edges. Let $C$ be the connected component that contains vertex $v_1$. I want to ...
0
votes
1answer
17 views

Number of ways to bicolor a graph with some constriants

Given a graph G, I need to find the number of ways to color it using two colors Black and ...
1
vote
0answers
25 views

Finding Smallest Frontier for Graphs of bounded pathwidth

Let $G$ be a graph and $X=x_1,x_2,...,x_n$ be an permutation/ordering of the vertex set of $G$. We then let $S_i = \{x_j:j\le i\}$, and $F_i$ be the number vertices $v\in S_i$ that are adjacent to ...
2
votes
0answers
29 views

Reducing Dominant Set Problem to SAT

I am trying to solve a problem and I am really struggling, I would appreciate any help. Given a graph $G$ and an integer $k$ , recognize whether $G$ contains dominating set $X$ with no more than $k$ ...
0
votes
1answer
52 views

Worst Case for AVL Tree Balancing after Deletion

After deleting a node in an AVL tree, self-balancing (zig-zag rotation or the left-right balancing) maintains O(logn) time that is not guaranteed in other unbalanced trees (like BST). The Balancing ...
1
vote
0answers
13 views

What is known about this independent set generalisation?

An applied problem I am working on could be modeled as the following problem on graphs: Given an undirected graph $G=(V,E)$ and an integer $k>0$, find the largest set $S\subset V^k$ such that for ...
1
vote
0answers
13 views

When would you use an edge list graph data structure instead of an adjacency list or adjacency matrix?

In what applications would you choose an edge list over an adjacency list or an adjacency matrix? Sample Question, VisuAlgo: Which best graph DS(es) should you use to store a simple undirected graph ...
2
votes
1answer
102 views

Runtime difference bewteen Union by Rank and Union by Size for union-find

I was studying Union Find, and according to Wikipedia, there are 2 types of union: union by rank and Union by size. My question is, what is the runtime difference between the two (if any)? Intuitively,...
1
vote
0answers
16 views

Number of graphs that satisfies the property that edge weight is maximum of node values on which the edge is incident

I have an undirected weighted graph without multi edges. All the edge weights are whole numbers and known. I want to know in how many ways node values(node values are also whole numbers) can be ...
2
votes
2answers
31 views

Label groups of vertices in a graph in an efficient manner without BFS/DFS

I have a graph with a set of vertices $\mathcal{V}$ and a set of edges $\mathcal{E}$. There exists a path between every 2 vertices in the graph. To each edge there is an associated weight $w(e), e \in ...
0
votes
0answers
13 views

graph augmentation problem for Regional-based connectivity

Region-based connectivity: Given a graph $G(V,E)$, $\lbrace R_1,..., R_{k}\rbrace$ is the set of all possible regions (A subgraph with diameter $d$ or a subgraph centered at a node with radius $r$) ...
0
votes
1answer
95 views

MIT 6006 Quiz 2: The shortest path task

I'm looking for some clarifications on an algorithmic task I've been trying to solve. This task is a part of Quiz 2 from the MIT 6.006 course. The main idea of creating ...
1
vote
1answer
72 views

Finding an MST with one adding and removing vertex operation

I am facing the following problem: Given an undirected complete Euclidean weighted graph $G(V, E)$ and its MST $T$. I need to remove an arbitrary vertex $v_i \in V(G)$, and given a vertex $v_j \notin ...
1
vote
1answer
69 views

Directed Grid Graphs; All Possible Paths Through Nodes

I have a problem in which I am interested in taking a matrix of positive integer weights, including zero, where the matrix has dimensions nrow x ncol and the columns always sum to the same arbitrary ...
1
vote
1answer
26 views

How can follow this this guide to construct a graph with matrix/reachability

Let's we have k matrices. For example we have 3 now, where first one is 8x5 ($a_1$ x $b_1$), second one is 5 x 6 ($a_2$ x $b_2$) and last one is 6 x 8 ($a_3$ x $b_3$). And our goal is to figure out ...
19
votes
8answers
4k views

Is Group Theory useful in Computer Science in areas other than cryptography?

I have heard many times that Group Theory is highly important in Computer Science, but does it have any use other than cryptography? I tend to believe that it does have many other usages, but cannot ...
5
votes
2answers
254 views

Graph coloring variation

Are there variations of the classic graph coloring problem that the number of neighbors in the same color is limited but not zero (in the original problem the limit is zero)? Problem: Given a graph $G$...
2
votes
1answer
37 views

Finding maximum subgraph with vertices of degree at most k

Let $G = (V, E)$ be an undirected graph and $U \subseteq V$ some subset of its vertices. An induced graph $G[U]$ is graph created from $G$ by removing all vertices that are not part of the set $U$. I ...
2
votes
0answers
26 views

Fastest Algorithm for finding All Pairs Shortest Paths on Sparse Non-Negative Graph

As discussed here Johnson's Algorithm can be used to solve the APSP-Problem in $O(V^2\log V + VE)$ in stead of $O(V^3)$ for Floyd-Warshall. However, Johnsons Algorithm does quite a bit of work for the ...
2
votes
1answer
39 views

Streaming algorithm for counting triangles in a graph

As described in the reference, the algorithm (see at the bottom) supposes to output an estimator $\hat T$ for the # of triangles in a given graph $G = (V, E)$, denoted $T$. It is written that "it ...
2
votes
1answer
21 views

Force-directed graph optimization with step-wise costs and constraints

Introduction I have an optimization problem. There are up to 25 nodes. The connectivity between the nodes is far less important than the Cartesian placement of the nodes. Since all nodes can ...
1
vote
0answers
146 views

Relation between sets of vertices in a graph

Suppose I have a graph with vertices of three colors - black, gray, and white. I want to compare the connectivity between sets of vertices to make claims like - the black set is more related to the ...
1
vote
1answer
46 views

Need hint for bipartiteness proof

I am given a graph $G = (V, E)$ with $N$ connected components and $G^\prime = (V^\prime, E^\prime)$, where for each $v \in V$ there is $v_1, v_2 \in V^\prime$ and for each $(u, v) \in E$ there is $(...
1
vote
0answers
27 views

Finding simple path on grid graphs of length $l$

Let $G$ be a grid graph. We are given two vertices $s$ and $t$, and an integer $l$. The goal is to check if there exists a simple path from $s$ to $t$ of length $l$. Brute force algorithm will give $n^...
1
vote
2answers
56 views

Coloring graph with constraints on assortativity

I have come across the following problem and I would love for your thoughts on an optimal solution or approximate calculations worth trying. The formulation of the problem in the form of graph theory: ...
4
votes
1answer
210 views

What is the goal of studying all those NP-complete problems?

So i'm currently reading a lot of things about graph NP-complete problems, and it seems that the goal of a lot of researchers is to find new results about their complexity, results like "...
1
vote
0answers
28 views

Finding the lengths at which cycles exist in a graph in parallel

I'm trying to find an algorithm that can find the lengths of simple cycles in an undirected graph in parallel that benefits strongly enough from it's parallelization to be practically more efficient ...
2
votes
1answer
31 views

Why minimum vertex cover problem is in NP

I am referring to the definition of the minimum vertex cover problem from the book Approximation Algorithms by Vijay V. Vazirani (page 23): Is the size of the minimum vertex cover in $G$ at most $k$? ...
0
votes
1answer
46 views

Solving the Knapsack problem in $O(n^2P)$, where P is the maximum weight of all items

Assume for the regular knapsack problem we have additional information - maximal weight of every item - lets denote it as P. Using this information, I want to solve the problem using dynamic ...
0
votes
0answers
53 views

Find every path that passes through certain edges

I'm faced with the following problem: Given Directed and unweighted graph, where each edge E has two attributes Goal Find every path through the 3 (or more) given edges in a specific order ...

1 2 3
4
5
78