All Questions

Tagged with
Filter by
Sorted by
Tagged with
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 ...

1
2 3 4 5
…
37