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
1
vote
0answers
29 views

Dijkstra's algorithm - additional properties

Say we let $R$ denote the set of currently chosen vertices in Dijkstra's algorithm, $d$ be the currently stored path-length estimates, and $s$ be the source. The standard property that we know is true ...
0
votes
0answers
19 views

Software for triangulation flip graphs?

I need to generate flip graphs on around 10 points (more would be nice). Specifically, I would like flip graphs on subsets of the integer lattice, so the coordinates of each point are integers. Is ...
3
votes
2answers
171 views

Shortest path including all nodes in a subset

Given a directed graph $G=(V, E)$, two nodes $s, t \in V$ and a subset of nodes $U \subseteq V$. Provide an algorithm that determines if there is a shortest path from $s$ to $t$ that passes via all ...
2
votes
0answers
105 views

Detecting cycles with weight zero in a directed graph

I am given a directed graph $G=(V, E)$ with a weight function $w: E\to\mathbb{R}$, that doesn't contain negative cycles. I need to find an algorithm that returns ...
1
vote
0answers
35 views

What does “yields” mean in the phrase *yields no back edges* in DFS?

What does yields mean in the phrase yields no back edges in the context of DFS? ...
1
vote
1answer
63 views

Triangles covering all vertices of a tri-partite graph

This question is an extension of this one: Min path cover for a three-layer graph with all paths traversing all layers. I'm designing fictional fruits. Each fruit has three attributes; color, taste ...
1
vote
1answer
89 views

What does Dijkstra's algorithm become, when you replace path cost with edge cost?

Consider a variant of Dijkstra's algorithm (for a directed graph) where nodes are visited not in order of total path cost, but in order of incoming edge cost. (Assume here that all edge costs are ...
0
votes
0answers
19 views

How to find diffrenet ways to implement merge and delete_min operation in binomial heap?

I have searched on the internet to find different ways to learn binomial heap operations. What I have found is not quite helpful for me.For example, for delete min operation the algorithm says: ...
2
votes
1answer
42 views

Find the set of all edges which there is a cycle such that for every $e' \in C, e'\neq e$ : $w(e')\leq w(e)$

Given an undirected graph $G=(V,E)$ and weight function: $ w: E \rightarrow \{1,2,...,10\}$. Describe an algorithm that finds the set of all edges $e\in E$ for which there is a cycle $C$ in $G$ that ...
1
vote
2answers
30 views

Given a list of vertices in a binary tree output minimal sublist with the same lowest common ancestor

The input: a binary tree and a list $L$ of vertices in that tree. The output: a sublist of $L$ of minimal length that has the same lowest common ancestor as $L$. If there is several sublists of ...
2
votes
0answers
32 views

find zero weight cycles in a directed graph [duplicate]

I need to plan an algorithm that decides if a directed weighted graph $G = (V,E)$ has a zero weight cycle. the graph has no negtive cycles the algorithm needs to be in $O(|V| \cdot |E|)$ time my ...
3
votes
1answer
46 views

A question about the work per recursive call in FPT vertex cover of size k algorithm

I have been looking at the FPT(Fixed Parameter) algorithm for checking if a vertex cover of size k exists.The algorithm goes as follows: VertexCoverFPT$(G, k)$ if $G$ has no edges then return true if $...
2
votes
1answer
49 views

Tight approximation for the chromatic number of an arbitrary graph in polynomial space and time

I am looking for an algorithm for approximating the chromatic number of an undirected simple graph with $n$ vertices in $O(n^{c_1})$ time and $O(n^{c_2})$ space, for some constants $c_1$ and $c_2$. ...
2
votes
1answer
44 views

How to avoid monochromatic cycles?

I am working on the following exercise: Consider a simple and connected undirected graph $G(V,E)$. Show that one can colour the edges of $G$ in polynomial time and with as few colours as possible ...
1
vote
1answer
36 views

How does node expansion work in a graph for AI search?

I want to try and write an example that solves the problem of travelling from one location to another described in the book AI: A modern approach. The problem involves getting from a particular city ...
2
votes
1answer
52 views

Optimization problem over bidirectional connected graph

A company has several automatic vertical warehouses (called elevators). Each elevator have several trays and each tray has several slots. A slot contains a given quantity of a given article. Elevators,...
0
votes
1answer
25 views

Algorithm of split graph $G=(V,E)$ to 2 groups that at least half of the edges are between the groups [duplicate]

Can someone remind me the algorithm that split vertex of graph to 2 groups that at least half of the edges are external, I mean between the groups. As I remember it was a greedy algorithm, each time ...
4
votes
2answers
69 views

How to make efficient path minimum queries in a tree?

Given a tree in which each node has a given value, I want to process "Path Minimum Queries": given two nodes, what is the minimal value of any node on the shortest path between them? My ...
2
votes
1answer
307 views

Is it possible to use an adjacency matrix for Bellman-Ford algorithm?

I have created a function that generates a complete, directed, and weighted graph, represented in an adjacency matrix but most Bellman-Ford implementations use an adjacency list. Is it even possible ...
0
votes
0answers
42 views

Most popular path in weighted cylic directed graph

Context I have a graph $G=(V,E)$ with weighted edges, all weights are positive integers $w(e)\in\mathbb{N}\setminus\{0\}$. The weights represent the popularity/count of each edge, for example $w(e) = ...
1
vote
0answers
23 views

Transforming a multidimensional 0-1 knapsack problem to a maximum weighted clique problem

Just out of theoretical curiosity, is there a way to transform a 0-1 multimensional knapsack problem to a maximum clique problem? Or maybe even easier, to a maximum weighted clique problem (the ...
1
vote
1answer
42 views

Approximate max weight path in directed graph

Context This question is related to the fact one can't use Bellman-Ford to find max weight paths in directed graphs with cycles. The reason is that giving a new graph $\tilde{G}$ with negative weights ...
2
votes
0answers
32 views

which algorithm GNU make uses to travel the dependency graph?

Make is a very common English word and consequently I cannot find the answer using google. I am writing a script to automate all the data generation process, which resembles what GNU make does. I am ...
1
vote
1answer
27 views

What does it mean that a set of intervals is sorted by the right and left endpoints?

While reading a paper (On the k-coloring of intervals), I came upon the following description: "Input: An integer k, and a set of n intervals sorted by right and left endpoints. The intervals are ...
2
votes
1answer
34 views

Which graph partitioning algorithm can solve this problem?

In brief: Here I have a cyclic graph above. I want to partition the graph vertices into 3 clusters. (With the mindset of cluster-wise "load balancing") ...
1
vote
1answer
29 views

minimum number of edges that should be added to an undirected graph to make it a tree

Basically, it's this rosalind problem. You're given a number of nodes and an adjacency list. My initial guess was that the answer was the number of connected components minus 1, since by joining every ...
0
votes
1answer
51 views

Two definitions of Safe Edge

I ran into an interview two days ago and came across one strange definition of safe edge. We are given an undirected weighted Graph $G = (V,E)$ with all distinct edge weights. Assume that the graph is ...
2
votes
1answer
33 views

Properties of Gomory-Hu trees

Given an undirected graph $G=(V,E)$ a Gomory-Hu tree $T$ for $G$ has the following properties: $T$ has a node for each vertex in the graph G and each edge in the tree corresponds to a minimum cut ...
0
votes
0answers
13 views

What's the best way to combine multiple A* searches?

I have a graph that looks like this The highlights nodes must be visited, and the blue node must be visited last, the stickman must be the start of the path. The weights are the Euclidean distance ...
1
vote
1answer
21 views

exists (u,v) edge with positive capacity and there is not path from $s$ to $u$. and $(u,v)$ is with full capacity in some maximal flow

Given a network flow and there exists (u,v) edge with positive capacity and there is not path from $s$ to $u$. and $(u,v)$ is with full capacity in some maximal flow. I've had this questions with ...
1
vote
1answer
45 views

Given an undirected graph, find an orientation such that every vertex has out-degree at least 3

Given an undirected graph $G=(V,E)$, describe an algorithm that computes an orientation of $E$ such that each vertex has out-degree at least 3. I know how to check if a vertex $v$ has at least $k$ ...
0
votes
2answers
38 views

Route finding on a graph that must go through multiple edges

I have this graph It shows a graph of a map that has nodes and segments (or edges), with weights, that connect these nodes. Some of these segments have addresses on, and some of these addresses are ...
0
votes
1answer
70 views

How to find every negative cycle in a graph

A graph with n vertices, no matter directed or not, may have maximally 2^n-n-1 negative cycles (Think about combination of 2 to n elements and you'll figure out why 2^n-n-1. A graph that has no graph ...
2
votes
2answers
79 views

Find maximal clique consisting of at least half of the vertices

Assume that we are given an undirected graph $G$ of n vertices. For this graph, we also know that there is a clique of size $c$, for some $c\geq \lfloor n/2 + 1\rfloor$. In other words, the majority ...
1
vote
1answer
119 views

NPC-problem reduction to triangle-free 3-colorability

lately, I have encountered a problem that I struggle to find a satisfactory solution for. I need to prove that triangle-free 3-colorability is NP-complete. Therefore I assume the right way is to find ...
0
votes
1answer
50 views

Reduce Clique to N-Degree-Clique

I want to show that there is a polynomial-time reduction from the standard $\text{Clique}$ problem to the $\text{N-Degree-Clique}$ problem, where: $$ \text{N-Degree-Clique} = \{ \langle G, k\rangle: \...
1
vote
1answer
64 views

facts on tree and MST

We are given an Undirected, Weighted and Connected Graph $G$, (non-negative weights, all distinct) with one property that shortest path between any two vertexes on this graph is on MST. The following ...
0
votes
0answers
29 views

The many strengths of Pagerank

PageRank is used and studied in incredibly many contexts. It is taught in many courses worldwide, with several books and thousands of papers devoted to it. To this regard, PageRank plays a quite ...
11
votes
0answers
105 views

Min-eigenvalue bound for a random d-regular graph

I need help proving the following fact: Let $G$ be a random $d$-regular graph with adjacency matrix $A$. The smallest eigenvalue $\lambda_n$ of $A$ should satisfy $|\lambda_n| = o_d(d)$. (In ...
1
vote
1answer
25 views

Complex/Hybrid data structures- do people ever combine structures like graphs and hash tables together?

I just built a LRU cache that combines a hash table and a double linked list. To me it was a brilliant idea to combine those two structures and use the strengths of each together, so it got me ...
0
votes
2answers
99 views

How to make a directed graph in python?

I am working on my own personal project. I took an intro to coding class last semester so I have been exposed to coding but I am still lost with it. Basically, for my project, I want to build a web ...
0
votes
1answer
32 views

why does relabel take O(VE) time total for unit capacity flow networks?

It is well known that for arbitrary flow networks, Goldberg's push-relabel algorithm takes $O(V^2E)$. Part of that comes from $O(V^2E)$ non-saturating pushes. Another part comes from $O(V)$ ...
2
votes
1answer
44 views

Graph partition that maximize the number of triangles within its parts

Given a graph $G = (V,E)$, how to partition $V$ into $k$ parts $P_1, P_2, \ldots P_k$ of at most $M$ vertices, such that the number of triangles (3-cliques) contained in the parts is maximal? This ...
5
votes
1answer
32 views

Quickly identify changes in connectivity

Given an undirected graph with at least one path connecting $u, v$, and a sequence of edges to be removed: $e_1, e_2, \dots$, I would like to quickly identify the point at which $u$ will be separated ...
1
vote
1answer
80 views

Question about the conditions to find articulation points in a graph

I have been reading a book called The Algorithm Design Manual by Steven Skiena and one of the topics discussed there is an algorithm to find all the articulation points in a graph. In it, we first ...
3
votes
0answers
82 views

Is there any polytime reduction from feedback vertex set to vertex cover?

I know that feedback vertex set (FVS) problem is $\mathrm{NP}$-complete since there is a simple and nice polytime reduction from vertex cover (VC) problem to FVS. Specifically, given a undirected ...
1
vote
0answers
62 views

How to prove that the pseudo-code of thresholded-A* algorithm from my teacher's book is correct?

I have the following DFS2 pseudo-code, which is used in the pseudo-code of IDA*, from my teacher's book, but I cannot understand why it's correct: ...
2
votes
1answer
22 views

Algorithm to convert many instances of unidirectional lists to a graph?

I feel like I'm missing something basic. I have instances of a list compromising of unique graph nodes / elements visited. Lists happen in order, but follow graph based rules (can be cyclical, only ...
9
votes
0answers
342 views

Shortest path that can be split into contiguous segments of 5 edges connecting 6 distinct nodes in an unweighted graph

The following problem (I'm paraphrasing) appeared in the 2019 Balkan Olympiad in Informatics: Five friends are on a road trip in a country with $N$ cities and $M$ bidirectional roads joining them. ...
2
votes
2answers
222 views

Partitioning a graph into subgraphs with overlapping nodes

I'd like to partition a graph into subgraphs with overlapping nodes. To do a simple partition into two, I could use kernighan_lin_bisection algorithm available in ...

1 2 3
4
5
82