All Questions
Tagged with algorithms graphs
1,841
questions
0
votes
0answers
27 views
Dynamic programming for graph splitting
I have a graph which has edges between every vertices $i$ and $j$ such
that $i < j$. I need to divide the graph into two parts such that the
sum of the weight of the edges traveling from the ...
1
vote
0answers
16 views
Can the Bellman-Ford Algorithm be used to find the longest path in an undirected graph through first negating the weight of all the edges? [duplicate]
I understand that the Bellman-Ford Algorithm can solve the single-source shortest-paths problem. However, can it also be used to determine the longest path in an undirected, graph through first ...
0
votes
1answer
20 views
Structural parametrization for weighted vertex cover
Let $G$ be a graph which is a tree with $\ell$ added edges. I wish to show that VWVC ((Vertex-)Weighted Vertex cover) is FPT with respect to $\ell$. In particular, I'd like an algorithm running in $O(...
2
votes
0answers
36 views
Optimal Item Locations given Traversal Paths
I have a given fully-connected undirected graph associated with (known) distances or alternatively a distance matrix, where the nodes or matrix rows/columns represent locations.
Additionally, I have a ...
0
votes
0answers
29 views
Minimum cost bin assignment
I've been trying to solve the below problem the entire day but couldn't come up with a solution. I have the suspicion that it could by solved by a graph algorithm (or maybe some greedy approach?) but ...
3
votes
0answers
36 views
Hardness of an instance of a problem independent of algorithms?
The paper “Where the really hard problems are” (https://www.ijcai.org/Proceedings/91-1/Papers/052.pdf) and others that cite it provide evidence that lots of algorithms for many NP complete problems (...
-1
votes
0answers
33 views
Assignment of Nodes to Multiple Queues
You are given $n$ customers at $n$ nodes and each node is at a variable distance away from all queues. Also each customer is processed in a constant amount of time $c$ when it is in a queue. Assuming ...
2
votes
0answers
28 views
Relationship between proof and algorithm of Ramsey's Theorem
The following is a problem statement from "Introduction to Theory of Computation" Chapter 0 Problem 0.14:
Let $G$ be a graph. A clique in $G$ is a subgraph in which every
two nodes are ...
1
vote
0answers
171 views
Total running time expressed in O notation of a word ladder program all words same length
I am trying to figure out a big O expression for the running time given $V,E,F$ for a word ladder or word chain program that I have written in Java. I am using undirected graphs with BFS.
What is ...
0
votes
1answer
34 views
Create Shortest Path tree for every node after Floyd Warshall in O(nm)
Right now I am stuck with the problem, how all shortest path trees can be created in O(n*m) given G = (V,E,c) with negative and positive costs without negative cycles and n =|V| m = |E| after ...
0
votes
0answers
13 views
Looking for a evolution/timeline algorithm
I am trying to draw a presentable timeline and I am doing some research about available algorithms
al
Here are the timelines of interest
I already found a great article by Bill Mill Drawing ...
5
votes
0answers
78 views
Scheduling tasks on a graph with assistance
This is a follow-up to a question that I recently posted here: Completing tasks on a graph. In that question, I posted the following:
Consider a graph $G = (V, E)$, where $V = \{0, 1, 2, \ldots, n\}$. ...
1
vote
2answers
35 views
Maximum matching for general graph
I am studying the maximum matching problem and I was trying to understand why the classical augmenting path algorithm does not work for the general graph (i.e. for non bipartite graph) and you must ...
1
vote
2answers
39 views
Selecting connected subgraph that exceeds value c, with least possible weight
Given a graph $G$ where each node has a value $c$ and weight $w$, I want to select a connected subgraph $V^*$, such that,
Sum of all values in $V^*$ crosses threshold $t$.
Sum of all weights(say $w^*...
1
vote
0answers
22 views
Finding s-t min-cut of undirected graph
Given an undirected graph with non-negative edge weights, and two vertices $s,t$ in the graph. I would like to find the minimal cut such that $s$ and $t$ are on different sides of the cut.
For example ...
1
vote
0answers
28 views
Equivalence of two approximation algorithms for min Steiner tree
I learned two approximation algorithms for the min Steiner tree:
The first algorithm:
1- Compute the metric closure G' of G.
2- Compute a min spanning tree T' of G'
3- Construct the union U of the ...
0
votes
0answers
79 views
Devise Mont Carlo and Las Vegas Algorithms to Solve Maximum Independent Set
I am trying to devise a Las Vegas algorithm to solve Maximum Independent Set, but I don't know how to start.
Also, I want to devise a Mont Carlo algorithm for this problem.
I would appreciate any help....
-1
votes
0answers
35 views
Finding a Spanning Tree Using other Spanning Trees of $G=(V,E)$
I am having trouble coming up with a polynomial time algorithm to solve the following problem:
Let $𝐺=(𝑉,𝐸)$ be an undirected and unweighted graph with $𝑛$ vertices. Let $𝑇_1,𝑇_2,...,𝑇_𝑘$ be $�...
-4
votes
1answer
31 views
Finding a clique in undirected graph is P or NP? (proof) [duplicate]
Finding a clique $C$ in an undirected graph $G= (V, E)$ such that $|C| > |V|/2$ is in P or NP-hard? How can I prove it?
0
votes
0answers
27 views
Cycles of a multigraph with a property on the edges
Let $n$ be a positive integer. On a circle are arranged $n$ points $A_1$, $\ldots$, $A_n$. We put some arrows from $A_1$ to $A_2$, from $A_2$ to $A_3$, etc., from $A_n$ to $A_1$. On each arrow are ...
3
votes
1answer
73 views
Completing tasks on a graph
Consider a graph $G = (V, E)$, where $V = \{0, 1, 2, \ldots, n\}$. The graph $G$ is complete, which means we can traverse $(i, j)$ for all $i, j \in V$. At each vertex $v \in V$, there is a task that ...
1
vote
0answers
26 views
Binary ↔ Gray permutation matrix
Generating a Gray code representation of a binary number can be thought of as mapping one binary number onto another binary number. Therefore, $n$-bit Gray code is a permutation of $2^n$ elements.
...
1
vote
0answers
27 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 ...
2
votes
2answers
125 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 ...
1
vote
1answer
83 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
18 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
39 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
29 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
29 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 ...
2
votes
1answer
51 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
23 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
64 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 ...
1
vote
1answer
51 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
39 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
1answer
29 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 ...
1
vote
1answer
26 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
31 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")
...
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
31 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 ...
1
vote
1answer
56 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 ...
3
votes
0answers
46 views
Bipartite graph projection, with threshold
Let $G=(\top,\bot,E)$ be a bipartite graph: $E\subseteq \top\times\bot$.
The projections $G_\bot = (\bot,E_\bot)$ and $G_\top = (\top,E_\top)$ of $G$ are defined as follows: two vertices are linked ...
1
vote
0answers
55 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
329 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
189 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
vote
1answer
53 views
Find Optimal Permutation/Positioning to Minimize the Total Distance for a Given Path
Summary:
A task for picking certain objects is given in the form of an ordered sequence (eg. to pick apple, banana, apple, apple, orange, order matters). The objects have to be preassigned to certain ...
0
votes
1answer
22 views
Floyd Warshall with constraints
I was wondering if its possible to use floyd warshall with constraints meaning lets say you have a group of "special vertices" of size logn and you want to calculate all the shortest paths ...
2
votes
3answers
241 views
For a binary tree of n nodes, there is a subtree with n/3 to 2n/3 nodes
in my notes I have one fact:
in a binary tree with $n$ elements ($n$ divisible by three) there is a node $u$ such that the number of nodes in the subtree with root $u$ is at least $\frac{n}{3}$ and at ...
