The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [graph-theory]

Questions about properties of and problems on graphs, discrete data structures that have the form of nodes connected by edges, that is networks.

1,692 questions
Filter by
Sorted by
Tagged with
37 views

Minimum Clique Cover - Mixed Integer Programming

I have a general (undirected) graph with a set of nodes, a set of edges, and a weight for each edge. I want to find a minimum clique cover of the graph, that is, a partition of the graph into the ...
20 views

Show that the de Bruijn graph G6,10 is strongly connected and balanced

I've been given this question and have absolutely no idea how to answer it. I can't even find the G6,10 graph nor have I been given it.
21 views

How can I avoid re-computation of Dijkstra algorithm if I add or remove one edge from a graph?

I have a nested graph filtration and each step I have to find the shortest path between two nodes. At each step I just add one edge to the graph so the re-computation of the Dijkstra algorithm is ...
41 views

binomial tree number of nodes

Does anybody knows that how we can assign number to nodes for binomial tree . I mean how we can represent the number of nodes by array? please give me hint I am really confused .
22 views

Existence of d-regular subgraphs in a k-regular graph

The claim is as follows: Let's say we have a $k$-regular simple undirected graph $G$ on $n$ vertices. Then, does $G$ then always have a $d$-factor for all $d$ satisfying $1 \le d \lt k$ and $dn$ being ...
49 views

How to encode reachability in a graph with walls as a SAT problem

Suppose we have a graph that represents a grid of cells. We are given a cell to start in and a cell that's the destination. There are cells that we cannot enter and they are known as walls. Finally we ...
50 views

Matching each unique pokemon with a unique move

Background: There are 832 unique Pokemon in the Pokemon universe, and There are 728 fighting moves that the Pokemon can collectively learn. No Pokemon can learn to do every fighting move, and some ...
38 views

What is minimum cost perfect matching problem for general graph?

It does make sense when we talk about perfect matching in bipartite graphs because there are two sets of points, for example, one set may be jobs and other set may contain different machines. But when ...
47 views

intervals in geometrical points in 2D space

Can anyone help me and provide me a link for learning geometrical points in 2d space which is related to algorithmic course ? this is the question but as I searched youtube there should be an equation ...
77 views

48 views

Minimal hitting set with respect to set inclusion from a book “Parameterized Complexity Theory”

In the first chapter of "Parameterized Complexity Theory" by Flum and Grohe, an example is presented to find a hitting set of minimal cardinality. In Fig. 1.3, the author says a black colored leaf ...
25 views

Why is the distribution of the clustering coefficient of a random network independent of degree?

I was reading about clustering coefficient distribution, and it seems that it is independent of node degree for the case of random networks, or even scale-free networks. I'm wondering why this is the ...
59 views

k-disjoint pair paths where any source can pair with any sink

I have a question regarding a problem I'm working on. The problem is given an MxN grid with k sources and sinks, find non intersecting paths (vertex disjoint) such that all sources are paired with a ...
22 views

Number of induced paths in an interval graph

Let $G$ be an interval graph. For any two vertices $u,v$ in $G$, how many induced paths are between them in $G$? Is it polynomial in terms of the number of vertices in $G$?
70 views

A question about Fleury's algorithm

The following is the Problem 1.4 in : Finding an Eulerian path. Show that if a connected graph has two vertices of odd degree and we start at one of them, Fleury's algorithm will produce an ...
26 views

Divide directed weighted graph into two parts

I have a directed, weighted graph $G = (E,V)$. For example, one might be $|E| = 74000, |G| = 725$. I want to divide this graph into two parts/clusters/communities, taking the edge weights into ...
46 views

Extracting a spanning tree from a directed acyclic graph with minimum total distance between terminal nodes

I have a directed acyclic graph that has uniform edge weights. I would like to extract from this graph a spanning tree (an arborescence) with the property that the total distance between all pairs of ...
33 views

Ford Fulkerson maximum flow for all vertices

Suppose we have a graph $G(E,V)$ with a source node $s$. Now for any $t\in V \setminus s$ I can find the maximum flow from $s$ to all possible $t$ by using the Ford Fulkerson algorithm $|V|-1$ times, ...
20 views

Network density vs connectivity

I was reading this paper where they mention about undirected networks: "The total connectivity of a network is defined as $C=\frac{E}{N(N-1)}$ where E is the number of edges and N the total ...
19 views

Greedy algorithm for feedback vertex set / greedy algorithms vs local ratio in general

A greedy algorithm for finding a minimum feedback vertex set is to pick and remove a vertex with minimum $w(v)/\delta_H(v)$, where $H$ is the current graph, until there are no more cycles left. (...
19 views

What is the approximation for odd cycle transversal?

What is the best approximation for odd cycle transversal? (on general graphs) Sorry if this is easily found everything I found about odd cycles is about paramaterized complexity and kernels