# Questions tagged [graphs]

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

4,666 questions
Filter by
Sorted by
Tagged with
2k views

### Tarjan's Strongly Connected Component algorithm

I am trying to understand Tarjan's strongly connected component algorithm and I have a few questions (the line numbers I am referring to are from Algoritmy.net): On line 33 why is ...
• 111
1k views

### Average length of s-t (simple) paths in a directed graph

Given the fact that $s$-$t$ path enumeration is a #P-complete problem, could there be efficient methods that compute (or at least approximate) the average length of $s$-$t$ path without enumerating ...
• 245
934 views

### Independent set where two vertices need to have distance >= c

An independent set (IS) in a graph is a set $V' \subseteq V(G)$ of pairwise non-adjacent vertices. I am interested in the generalization $c$-IS where two nodes in $V' \subseteq V(G)$ need to have ...
• 783
69k views

### Difference between cross edges and forward edges in a DFT

In a depth first tree, there are the edges define the tree (i.e the edges that were used in the traversal). There are some leftover edges connecting some of the other nodes. What is the difference ...
• 1,123
1 vote
103 views

• 2,269
68 views

### The name of "finding the path of a graph that is a variant of hamiltonian path" [duplicate]

Suppose that there is some graph, with $n$ vertexes. We wish to find the hamiltonian path, but we make the graph being searched a little different. There is a person A that travels each (undirected) ...
• 101
4k views

### What is the maximum number of shortest paths between any pair of vertices in a chordal graph?

A graph $G$ is chordal if it doesn't have induced cycles of length 4 or more. Chordal graphs are precisely the class of graphs that admit a clique tree representation. A clique tree $T$ of $G$ is a ...
• 22.3k
374 views

### How do we know to what community a vertex belongs to in the Girvan-Newman algorithm?

So I've been doing some reading on community detection in graphs as I'm planning on working on my thesis for it. I've been reviewing papers regarding the same and came across the Girvan-Newman ...
• 314
2k views

### Acyclic Tournament Digraphs and Hamiltonian Paths

I am studying MIT OCW lecture notes but they do not have solutions for the following problem. Directed Acyclic Tournaments In a round-robin tournament, every two distinct players play against each ...
• 31
1 vote
60 views

### $st$-path with fewest leaving edges

Given an undirected unweighted multigraph $G=(V,E)$ and $s,t \in V$ find a simple $st$-path $P$ s.t. the number of edges leaving $P$ (i.e. the edges with exaclty one endpoint in $P$ ) is minimized. ...
• 783
24k views

### Number of cycles in a graph?

Can the number of cycles in a graph (undirected/directed) be exponential in the number of edges/vertices? I'm looking for a polynomial algorithm for finding all cycles in a graph and was wondering if ...
• 277
461 views

### Number of Hamiltonian cycles on a Sierpiński graph

I am new to this forum and just a physicist who does this to keep his brain in shape, so please show grace if I do not use the most elegant language. Also please leave a comment, if you think other ...
• 291
6k views

### How to find the maximum independent set of a directed graph?

I'm trying to solve this problem. Problem: Given $n$ positive integers, your task is to select a maximum number of integers so that there are no two numbers $a, b$ in which $a$ is divisible by $b$...
• 255
4k views

### Longest path in undirected tree [duplicate]

Given an undirected tree (with no specific root), how to find the longest path, i.e. 2 vertices that are the farthest apart from each other? There are no lengths associated with the edges (each edge ...
• 109
2k views

### Find node that splits tree in half

Given a tree $T = (V , F)$, find an algorithm which finds $u \in V$, so in the graph $T = (V \setminus \{u\} , F)$ the size of each connected component is $\lceil |V| / 2 \rceil$ at most. What is the ...
16k views

### What is the complexity of this matrix transposition?

I'm working on some exercises regarding graph theory and complexity. Now I'm asked to give an algorithm that computes a transposed graph of $G$, $G^T$ given the adjacency matrix of $G$. So basically I ...
• 213
11k views

### How to find a local minimum of a complete binary tree?

How to find a local minimum of a complete binary tree? Consider an $n$-node complete binary tree $T$, where $n = 2^d − 1$ for some $d$. Each node $v \in V(T)$ is labeled with a real number $x_v$. ...
• 269
41k views

### Is Dijkstra's algorithm just BFS with a priority queue?

According to this page, Dijkstra's algorithm is just BFS with a priority queue. Is it really that simple? I think not.
1 vote
120 views

• 243
13k views

### The purpose of grey node in graph depth-first search

In many implementations of depth-first search that I saw (for example: here), the code distinguish between a grey vertex (discovered, but not all of its neighbours was visited) and a black vertex (...
• 333
3k views

### Why doesn't the Floyd-Warshall algorithm work if I put k in the innermost loop

The Floyd-Warshall algorithm is defined as follows: ...
• 333
1k views

### Are link-cut trees ever used in practice, for max flow computation or other applications?

Many max flow algorithms that I commonly see implemented, Dinic's algorithm, push relabel, and others, can have their asymptotic time cost improved through the use of dynamic trees (also known as link-...
• 301
1 vote
451 views

### Dfs algorithm and cycles question

Is it true or false that for running a dfs on an undirected graph G with a simple cycle than this cycle will have exactly one back edge? Looks to me likes its true ,is it?
1 vote
150 views

### Path on an edge-colored DAG using exactly $k$ colors

I have the following problem: Given an edge-colored DAG $G = (V,A)$, vertices $s$ and $t$, a set of colors $C$ and $k \in \mathbb{N}$, does there exist a path from $s$ to $t$ using exactly $k$ ...
5k views

### What's the complexity of calculating the shortest path from $u$ to $v$ with Dijkstra's algorithm using binary heap?

Problem: Consider a graph $G = (V, E)$ on $n$ vertices and $m > n$ edges, $u$ and $v$ are two vertices of $G$. What is the asymptotic complexity to calculate the shortest path from $u$ to $v$ with ...
• 1,615
3k views

### Uniform-cost Search Problem

Suppose that we take an initial search problem and we add $c > 0$ to the costs on all edges. Will uniform-cost search return the same answer as in the initial search problem? Definitions: Uniform-...
• 51
2k views

### Finding all cliques of a graph

Given a graph with $n \leq 50$ vertices. Count all $k$-cliques of this graph, where $k = 1, \ldots , n$. I need the most efficient algorithm.
424 views

### BFS in K shortest paths

Do we need to use BFS or DFS algorithm to find the k shortest loopless paths in a graph between any two nodes? If so where can it be useful?
• 39