# Questions tagged [graphs]

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

4,194 questions
Filter by
Sorted by
Tagged with
68 views

21k views

### Finding a source of a directed acyclic graph in linear time

Given a directed acyclic graph $D = (V,A)$, a vertex $v \in V$ is a source if its indegree is zero, meaning that it has only outgoing arcs. Does there exist a linear time algorithm to find a source ...
2k views

### Is there a non-brute force algorithm for Eulerization of graphs?

Given some undirected, unweighted, connected, and potentially parallel-edged graph $G$, an Euler circuit may be constructed iff every vertex in $G$ has an even degree. In graphs with two or more ...
602 views

### Why not relax only edges in Q in Dijkstra's algorithm?

Can someone tell me why almost in every book/website/paper authors use the following: foreach vertex v in Adjacent(u) relax(u,v) when relaxing the edges, ...
702 views

### Visualized definition of cohomology

I cannot imagine how cohomology is related to graph theory, actually I read solid definition from wiki, and to be honest, I cannot understand it. e.g I know what is homotopy (in simple term), group ...
1k views

### Using transitive closure to determine acyclic property on directed graph

Is it possible to use Warshall's algorithm (calculating the transitive closure) to determine if a directed graph is acyclic or not? I'm trying to achieve this but getting stuck on the reflexive ...
447 views

### Maximimal Independent Set on Ring and Path

Let's consider distributed version of algorithm for finding MIS of any graph $A$. For details, MIS - Maximimal Independent Set. Slow version of distributed algorithm for MIS, page 2 - Distributed ...
145 views

### Graph Bipartiteness

I have 2 questions regarding Bipartiteness with corresponding examples. 1) Can a non-connected graph be bipartite if it has an isolated vertex? Let's take the following graph: I would say YES with ...
127 views

### Heuristics for tree decomposition into k shortest paths

What kind of heuristics are useful in a tree decomposition of a graph to find the k shortest paths from a given source to a vertex? Moreover, the local shortest paths at each node in a tree are ...
191 views

### Application of Expander Codes

I need to give a talk about expander codes at university (I'm a student of computer science). Since they have been introduced to show a family of codes looking good when thinking of the Shannon ...
207 views

### Non-deterministic algorithm for solving figure of 8

I am struggling in trying to figure out a non-deterministic algorithm for the following problem. Consider the following problem, called the ﬁgure-of-eight problem (FOE). An instance is an undirected ...
10k views

### DFS - Proof of Correctness

I'm currently studying the book "Introduction to Algorithms - Cormen". Although a proof of correctness for the BFS algorithm is given, there isn't one any for the DFS in the book. So I was courious ...
3k views

### Generating a adjacency matrix representing a DAG

Does anyone have a pointer to a resource or, even better, a tip to provide on how to efficiently generate a very large matrix representing a connected graph. Graph can be randomly created although I ...
207 views

### How is a star topology a regular graph?

A regular graph is one in which each vertex has the same number of neighbors, but in a star topology the central vertex is connected to more than one vertex. So, why is it referred to as a regular ...
4k views

### Why we do isomorphism, automorphism and homomorphism?

What are the key differences between these three terms isomorphism, automorphism and homomorphism in simple layman language and why we do isomorphism, automorphism and homomorphism ?
20k views

### How to understand the reduction from 3-Coloring problem to general $k$-Coloring problem?

3-Coloring problem can be proved NP-Complete making use of the reduction from 3SAT Graph Coloring (from 3SAT). As a consequence, 4-Coloring problem is NP-Complete using the reduction from 3-Coloring: ...
7k views

### Dijkstra's algorithm for undirected graphs with negative edges

INPUT: "an undirected, weighted graph (negative weights allowed)" Could someone give an example for an undirected graph with negative edges where Dijkstra's algorithm doesn't work? As far as i ...
29k views

### What is the fastest algorithm for finding all shortest paths in a sparse graph?

In an unweighted, undirected graph with $V$ vertices and $E$ edges such that $2V \gt E$, what is the fastest way to find all shortest paths in a graph? Can it be done in faster than Floyd-Warshall ...
255 views

### Is it possible to use plants as a medium to store data? By what data structure?

my question is simple. Is it possible to use plants as a medium to store data? My opinion is: Possible, but we need to solve, how to distinguish 2 states. Duplication and CRC of stored DATA is quiet ...
614 views

### Random graph model

When we say that in random graph we add an edge with a certain fixed probability, what do we actually mean? For example if probability is 0.5, does that mean that we can just add two edges in a graph ...
I saw in this video that computing clustering coefficient of central node of a star graph using the following algorithm is $\Theta(n^2)$ and for a clique it is $\Theta(n^3)$. is that correct? ...