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
0answers
68 views

Complexity of computing the first bits of a minimal permuted adjacency matrix

Given any graph $G$ on $V(G)=\{1,\dots,n\}$ and its adjacency matrix $$A(G)=\left(\matrix{ A_{1,1} & A_{1,2} & \dots & A_{1,n}\\ A_{2,1} & A_{2,2} & \dots & A_{2,n}\\ &&...
0
votes
0answers
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) ...
6
votes
1answer
3k 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 ...
3
votes
1answer
328 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 ...
3
votes
2answers
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 ...
1
vote
1answer
59 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. ...
4
votes
2answers
20k 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 ...
18
votes
1answer
421 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 ...
7
votes
1answer
5k 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$...
0
votes
2answers
3k 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 ...
4
votes
4answers
1k 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 ...
6
votes
2answers
13k 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 ...
8
votes
1answer
9k 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$. ...
30
votes
2answers
37k 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
2answers
114 views

Prove that $0$-$1$ $\mathsf{ Ineq}$ is $\mathsf{NL}$-complete

I need to prove that the following problem $0$-$1$ $\mathsf{ Ineq}$ is $\mathsf{NL}$-complete. Given a finite set of variables $V$, a finite set of inequalities of the form $x \le y$ (where $x, y \in ...
1
vote
1answer
134 views

Prove that 2-Colourability is in L from Undir-Reachability is in L

Let Undir-Reachability be the following problem: given an undirected graph G and two specified vertices s and t in G, is there a path from s to t in G? I need to prove that the 2-Colourability is in ...
2
votes
0answers
227 views

Travelling salesman problem with detours

I am interested if there exists a following version of the travelling salesman problem: INSTANCE: A finite set $C = \{1,2,\dots,k\}$ of cities, a positive integer distance $\delta(i,j)$ for each pair ...
4
votes
1answer
143 views

Bipartite graph question

Assume you are given a bipartite graph $G = (U, V, E)$ and you are given an integer $n$. Assume also that for each $v \in V$, you are given two integers $v_{min}$ and $v_{max}$ (where $v_{min} \le v_{...
22
votes
4answers
11k 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 (...
9
votes
4answers
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: ...
20
votes
2answers
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-...
1
vote
1answer
423 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
1answer
142 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$ ...
4
votes
1answer
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 ...
4
votes
2answers
2k 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-...
2
votes
1answer
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.
-1
votes
3answers
394 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?
3
votes
0answers
138 views

Maximal value of directed graph with constraints

What is an algorithm to calculate the maximum "score" possible in a directed graph, with the constraint that edges with the same value can only be traversed once? For example, in the graph ...
0
votes
1answer
130 views

Push relabel algorithms in flow networks

In the CLRS book (http://en.wikipedia.org/wiki/Introduction_to_Algorithms) Chapter 26 (Maximum Flow) page 744 (third edition), there is the following equation - $$ \sum_{u \in U}e(u) \;=\; \sum_{u \...
13
votes
4answers
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 ...
7
votes
1answer
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 ...
5
votes
2answers
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, ...
4
votes
1answer
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 ...
2
votes
2answers
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 ...
2
votes
1answer
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 ...
0
votes
1answer
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 ...
2
votes
0answers
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 ...
5
votes
1answer
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 ...
2
votes
1answer
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 figure-of-eight problem (FOE). An instance is an undirected ...
1
vote
3answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
14
votes
2answers
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 ?
8
votes
3answers
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: ...
4
votes
3answers
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 ...
25
votes
3answers
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 ...
1
vote
1answer
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 ...
1
vote
3answers
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 ...
2
votes
1answer
652 views

Bellman-Ford: shortest path

my assumption: - we have an undirected graph with only positive edges - the edges are sorted alphabetically:     e.g A-B, A-C, B-D     and e.g not C-A, D-B, A-...
1
vote
1answer
3k views

Computing the clustering coefficient

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? ...

1
78 79
80
81 82
84