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
0
votes
0answers
8 views

A DFS update without re-running DFS after adding and removing an edge

Given an undirected graph $G=(V,E)$ I perform a DFS run on it, and among other information I get the visit time $s(\cdot )$ and the exit time $f(\cdot )$ per each node and the parent of each node. ...
1
vote
0answers
28 views

Graph in which greedy algorithm for maximum matching is a 2-approximation

Here is a greedy algorithm for maximum bipartite matching: Iteratively select an edge that is not incident to previously selected edges. This algorithm returns a 2-approximation, and runs in linear ...
2
votes
1answer
46 views

Maximum independent subset for graphs with lots of edges

Consider an NP-hard graph problem, like the maximum independent set problem. Let us say I restrict my inputs to only be graphs that have $n$ vertices and at least $n^{c}$ edges, for some $c > 1$. ...
1
vote
1answer
18 views

Reducing a seating problem to maximum flow

Problem: We have p different families with $1 \leq i \leq p$ members for the $i$-th family. We also have q tables where table $t_j$ has a capacity of $1 \leq j \leq q$. We want no two members of a ...
2
votes
1answer
31 views

Minimum number of edges to remove from a graph, so that MST contains a certain edge

Let's suppose we have a weighted and connected graph. We can easily find the minimum spanning tree for this graph. But let's say we want to "force" a certain edge $e$ to be in the MST. For ...
0
votes
0answers
12 views

Detect the actual edges of circle in directed graph [duplicate]

Okay so , I know how bellman -ford can detect a negative circle. My question is : how to actually find the edges participating in this circle. I searched and found some stuff that seem to work in the ...
1
vote
0answers
15 views

How to find if there's an MST where vertex $v$ has degree 2 in it? [duplicate]

I've faced this question and I hope that someone can help with it. Question: We're given an undirected graph $G=(V,E,w)$ where $w\colon E\rightarrow \mathbb{Q}$ and vertex $v$. We want to find if ...
-1
votes
0answers
49 views

Maximum flow: Dining problem

I have a network flow problem: There are $n$ people invited to a party, the age of person $i$ is $a_i$ years, the waiter must position them in a way such that: Everyone sits around a table There are ...
1
vote
0answers
25 views

Graph based on strings of turing machine

For a $\Sigma$ with characters $0,1,$#$,\sigma_1,...,\sigma_m$. I have any $M$ that is a deterministic turing machine. Fix a $n$ (natural). i look at the following graph constructed from the turing ...
1
vote
1answer
34 views

Fastest way to find optimal graph coloring in polynomial space given chromatic number

Suppose I have a graph's chromatic number. Give a faster-than-brute-force polynomial-space algorithm for finding an optimal coloring. If such an algorithm isn't known, please tell me so. This question ...
0
votes
1answer
18 views

About a possible optimized version of Johnson's algorithm on a DAG with "elementary circuits"

Recently I came upon the Johnson's algorithm to find "elementary circuits" on a directed graph, which is really cool to me. I'm just implementing it from scratch in C++ following the ...
1
vote
1answer
18 views

Current state of polynomial-space exact graph coloring

The fastest algorithm I could find that finds the chromatic number of an undirected simple graph exactly in only polynomial-space is "Faster Graph Coloring in Polynomial Space" by Gaspers ...
2
votes
1answer
42 views

Algorithm for finding subsets subject to union condition

I'm a mathematician and the following came up in my research: Fix some positive integers $a_0,...,a_n$ and $N$. Consider subsets $A_i \subset \{0,...,N\}$ where $|A_i|=a_i$, subject to some fixed ...
0
votes
0answers
55 views

How to solve a specific dining problem with max flow network?

n people named i are invited to a party. They are a(i) years old. We want to position them on some tables by obeying the following criteria: Each guest must sit around a table. Each table should have ...
2
votes
1answer
28 views

Set of Pareto-optimal paths, in a graph where edges have both length and cost

Suppose I have a graph $G=(V,E)$, where each edge $e$ has both a non-negative length $\ell(e)$ and a non-negative cost $c(e)$. Given a start node $s$ and a destination node $t$, I want to find a set ...
2
votes
1answer
24 views

Retrieving the cheapest path of a graph with time-dependent edge weights

There are many efficient algorithms for finding the shortest path in a network, like dijkstra's or bellman-ford's. But what if the weights of edges are time-dependent? I'm trying to find an efficient ...
6
votes
2answers
224 views

What edges are not in a Gabriel graph, yet in a Delauney graph?

It is know that the Gabriel graph of a point set $P \subset \mathbb{R}^2$, $\mathcal{GG}(P)$ is a subset of the corresponding Delauney graph $\mathcal{DG}(P)$, i.e. $\mathcal{GG}(P) \subseteq\mathcal{...
0
votes
1answer
60 views

How to find the maximum number of square groups in a board

I'm stuck with the following problem: Given an n*m board, find the maximum number of square groups that can be positioned on the board. What are square groups? They contain 4 distinct squares named: ...
4
votes
2answers
60 views

Generating Isomorphic Graphs

Is there a way of generating random isomorphic graphs for the purposes of testing tools like Nauty or BLISS? Every paper I've found says the authors had a database of certain isomorphic graphs, but I ...
1
vote
0answers
37 views

Algorithm for finding a specific ordering of nodes in a graph $G=(V, E)$ in $O(|V|+|E|)$ time

I have an undirected graph $G=(V,E)$ and I want to find an ordering of $V$, $\pi=(v_1, v_2, ..., v_n)$, such that for each $1 \leq i \leq n$, $v_i$ is of minimum degree in the subgraph $G_i = [\{v_1, ....
0
votes
0answers
18 views

Task assignment using directed graph

Here's a problem that uses graph to find task assignment among a group of workers. Assume there are N number of tasks to be completed, with dependencies among the tasks. For example, task i depends on ...
4
votes
1answer
36 views

How can we process these types of queries on trees?

CAN SOMEONE FIND A BETTER (MORE DESCRIPTIVE) NAME FOR THIS QUESTION, THANKS I recently thought of this interesting Tree problem: Given a tree with $N$ nodes, let $val_i$ = the "value" for ...
0
votes
0answers
31 views

finding all vertices on a negative cycle using belman ford twice

We are given that the following algorithm finds the vertices inside a negative cycle and we need to show an example for it such that it fails. ...
0
votes
0answers
31 views

I do not understand a way of proving the correctness of the algorithm to compute the Strongly Connected Components

"Introduction to algorithms" also known as CLRS, proves the correctness of the algorithm to compute the Strongly Connected Components in two ways, one of which is Here is another way to ...
6
votes
1answer
79 views

Archaeological Consistency: Graph Problem

So, I have an issue with the following problem (CS 161 Stanford 2013, Problem Set 2): Suppose that you have found a collection of historical records indicating the relative order in which various ...
2
votes
0answers
18 views
2
votes
1answer
37 views

Edmonds Karp time complexity based on graph's diameter

Suppose we have a graph such that we want to apply a maximum flow algorithm(for example Edmonds Karp) on it. And suppose we only know that graph's diameter is 70 so we want to calculate that's time ...
2
votes
1answer
34 views

find vertex cover of size at most 30 of a graph

This is a question from an exam I got wrong. Given an undirected graph $G$. Consider the decision problem of finding if there exists a vertex cover of size at most 30. Can we find a polynomial time ...
4
votes
0answers
60 views

Generating graphs with partially overlapping cliques

Currently, I am working on a research project where I will utilise reinforcement learning for the diversified top-$k$ clique search problem. To train the reinforcement learning algorithm, I need to ...
3
votes
1answer
36 views

When inserting a new vertex in a DAG, what possible changes are there to the edges

Background: I'm trying to program a generic method to add a node to a Directed Acyclic Graph. This method should allow the caller to specify the possible effects on the graph, specifically the edges. ...
0
votes
1answer
31 views

What is the relation between Topological Sort and Strongly Connected Components?

Both the Topological Sorting algorithm and the algorithm to find Strongly Connected Components build a stack whose top is the last visited vertex. I find difficult to find an explaination because ...
0
votes
0answers
16 views

Object Visibility Graphs

I have gone through this defination A graph G = (V, E) is called an object visibility graph if there is a set of non- intersecting objects so that there is a one-to-one correspondence between the sets ...
2
votes
1answer
61 views

Why the choice of the adjacent vertex with the least degree is a good heuristic for the hamiltonian path problem?

Even if the hamiltonian path problem is NP-hard there exist heuristics which return a correct path for many instances in linear time. In particular one of the main rules is always choosing the ...
2
votes
0answers
24 views

On the complexity of equitable $k$-coloring split graphs

The Wikipedia article on Equitable coloring states that A polynomial time algorithm is known for equitable coloring of split graphs. The referred paper also seems to achive the proposed polynomial ...
10
votes
4answers
2k views

Why are graphs represented as adjacency lists instead of adjacency sets?

In answering this question, I was looking for references (textbooks, papers, or implementations) which represent a graph using a set (e.g. hashtable) for the adjacent vertices, rather than a list. ...
2
votes
0answers
48 views

Finding the cut with the minimum number of edges (including reverse ones)

I do not know how to solve the following problem: Given a directed graph $G$ with a two nodes $s,t \in V(G)$ find a cut $(S,T)$ with $s \in S$ and $t \in T$ such that $(S,T)$ has the minimum number of ...
3
votes
2answers
116 views

Maximum planar subgraph problem

Given a graph G I want to find the maximum planar subgraph which is a grid graph. (Because the nodes of this subgraph represent points on a grid). Is there any library in python for finding the ...
4
votes
1answer
74 views

Warnsdorff's rule: more errors with odd sized boards

I wrote an algorithm based on the Warnsdorff's rule to solve the knight's tour problem, where you need to create a sequence of moves of a knight on a chessboard such that the knight visits every ...
-3
votes
1answer
32 views

Edge included in all the minimum spanning tree if it is included in at least 2 minimum spanning tree

Is it true that if an edge is included in at least two different minimum spanning tree, then that particular edge is included in all minimum spanning tree? If so why?
1
vote
0answers
67 views

A Special Case of Set Cover Problem: Covering Nodes of Tree using Paths [closed]

Let $U$ be the set of elements and $S$ be the subset collections. There exists a tree $T$ that each node is corresponding to an element in $U$. And for every subset $s$ in $S$, $V(T) \bigcap s $ is a ...
1
vote
1answer
155 views

Algorithmic Problem on Trees

Given a directed, rooted tree with $n$ vertices, the height of a vertex $v$, $h[v]$ is the number of edges on the longest path from $v$ to some reachable leaf node. Give an efficient algorithm to find ...
1
vote
0answers
25 views

Cluster 3d points with constraints

I have some 3d point cloud I wish to cluster into some number of clusters. I have the probability of two points being in the same cluster given as some function of their relative locations, with the ...
7
votes
11answers
4k views

Real life examples of *zero* weight edges in graphs

The meaning of edges with zero weight in a weighted graph questions me for a long time, and I even asked a related question previously. Yet, when I recently read here a question on real life example ...
2
votes
0answers
30 views

Why is $O(nk)$ an upper bound for the $k$-gossip problem?

I am studying the $k$-gossip problem on dynamic graphs against an adaptive adversary. Essentially, we are given a set of tokens $\mathcal{T}$ which are distributed amongst the nodes such that each ...
3
votes
1answer
58 views

Shortest possible path between closest pair of specific nodes in a maze

Need to find the shortest distance between the closest pair of 'r' and 'b' nodes. You can traverse along '.' elements, but not 'o' elements. How can we do this in $O(MN)$ time? (M rows, N cols). $O(...
0
votes
0answers
22 views

Minimum spanning tree containing specific edges

Given a weighted undirected graph and a list of edges (without cycles), how can I create an MST that contains all those edges (or says that such an MST does not exist)?
6
votes
1answer
287 views

Fast and compact data structure for dynamic graphs

A graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ may be represented in central memory as follows: an associative array (hash table) $V$ gives for any $v\in \mathcal{V}$ the list of its neighbors $V[v]$...
18
votes
6answers
3k views

Real life examples of negative weight edges in graphs

I am unable to relate to any real life examples of negative weight edges in graphs. Distances between cities cannot be negative. Time taken to travel from one point to another cannot be negative. ...
2
votes
1answer
35 views

What Graph Algorithm can determine ideal distribution of items to travel the least amount of distance from any node?

I have a problem that's been bugging me, but I'm not sure what algorithm can solve it. Alice has medicine that she needs to use as quickly as possible in case of an allergy attack. She wants to ...
2
votes
0answers
17 views

UCYCLE in LOGSPACE and linear time

Consider UCYCLE, the problem of recognizing undirected graphs containing a cycle. On the one hand, it's in LOGSPACE, see this stackexchange thread: start at every vertex $v$ a DFS and check whether it ...

1
2 3 4 5
87