# Questions tagged [graphs]

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

3,856 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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$ ...
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 ...
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?
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 ...
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.  I'm looking for a formulation of the problem that allows for path-...
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\...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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$ ...
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 ...
13 views

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 ...
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 ...
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,...
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 ...
31 views

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 ...
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 ...
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 ...
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$...
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 ...
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 ...
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 ...
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 ...
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 ...
46 views

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: ...
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 "...
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 ...
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$? ...