Skip to main content
Share Your Experience: Take the 2024 Developer Survey

All Questions

Tagged with
Filter by
Sorted by
Tagged with
0 votes
0 answers
10 views

Minimum cost hamiltonian path of length K over any subset of nodes in a graph

I came across a situation in real life that maps to this optimization problem: Across all Hamiltonian paths of length $K$ in a fully connected, undirected graph with $N \ge K$ edges, find the one ...
InfiniteSnow's user avatar
1 vote
0 answers
16 views

Global minimum weighted vertext cut for undirected graphs

Given an undirected graph with vertex weights, there any algorithm for finding the global minimum vertex cut that partitions the graph into two components? I can transform the graph to directed one ...
tr244's user avatar
  • 11
0 votes
0 answers
8 views

Managing hashing overlaps (building a heuristic for the edge of a 3x3x3)

I'm trying to build a 3x3x3 solver for a school project. I got inspired by Ben Botto's solver, which you can find here. Such as Ben does with his solver, I'd like to implement Korf's heuristic ...
AlioTheCat's user avatar
0 votes
1 answer
34 views

Balancing tree by removing nodes instead of perfoming rotations to defined height $h$

I am provided a tree that may be very deep and unbalanced. I want to be able to transform this tree into a more balanced form with maximum height $h$. We can do this by removing internal nodes, but we ...
olivarb's user avatar
  • 101
1 vote
1 answer
21 views

Pseudo-Traveling Salesman on a colored graph

I have a graph with nodes of various colors and weighted edges between them. I would like to find the least cost path that touches exactly one node of each color. Is this a known problem or reducible ...
Jemmy's user avatar
  • 113
4 votes
0 answers
42 views

Algorithm for finding a path factor in a graph

A 1-factor is a perfect matching. A path factor of a graph $G$ is a spanning subgraph, each of whose components is a path with at least two vertices (see the following figure). Since every path with ...
licheng's user avatar
  • 405
1 vote
1 answer
183 views

How to solve a system of XOR equations in a cyclic graph?

I am working on a problem where I need to find values for nodes in a graph of k-nodes. Here an example: The properties are: Each big node (A..H) is connected to at least one blue node Each blue node ...
nowox's user avatar
  • 241
0 votes
1 answer
30 views

Robust maximum weight forests with weights on edges

In an undirected weighted graph with edge weights, the task is to find a spanning tree T. An adversary will delete two edges (not necessarily from T), and subsequently, we can add an edge (excluding ...
Toyllo's user avatar
  • 1
3 votes
0 answers
50 views

Algorithm to find minimum number of cuts in DAG based on a rule

I encountered this problem while doing some “graph”ics programming: Take a directed acyclic graph where every vertex is given a non-unique label 1..N You can ‘trim’ the DAG by making a cut that ...
Matt Tytel's user avatar
1 vote
1 answer
93 views

Number of unique paths in a grid

Suppose, I have a nxn grid. Now, I want to move from (1,1) to (1,n). How many unique ways are there possible if I can move in left, right, up and down direction. I am trying to solve it using depth ...
Nakib's user avatar
  • 11
0 votes
0 answers
9 views

Shortest path in a graph where edge weights can vary dynamically based on the path taken [duplicate]

I have a directed acyclic graph whith negative edges where edge weights can vary dynamically based on the path taken. ...
user1552545's user avatar
0 votes
0 answers
16 views

Kernelization For Odd Cycle Transversal Problem on Perfect Graphs

This problem appears as exercise 2.33 in https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf (page 48). A perfect graph $G$ is bipartite if and only if it contains no triangle graphs. ...
Yavuz Bozkurt's user avatar
0 votes
1 answer
32 views

Will CSR format store the all 0 column?

In the matrix(3 rows and 7 columns) below with 4 all zero columns 0 4 0 0 0 0 0 2 1 0 0 0 0 0 0 0 3 0 0 0 0 The CSR format of storage is : row_ptr: [0, 1, 3, 4] col_ind: [0, 0, 1, 2] values: [4, 2, ...
san zhang's user avatar
0 votes
1 answer
32 views

Is this depth search correct (DFS) Shouldn't one act according to the LIFO principle?

Shouldn't we actually continue with C after A, thought a depth search, follows the LIFO principle, isn't C the last node added in this case and shouldn't we expand C before B?
test's user avatar
  • 1
0 votes
1 answer
18 views

Assigning classes to nodes in a graph to minimise intra-class distance

I have an complete undirected graph with n vertices, and the edge $(u,v)$ has weight $d(u,v)$ for some distance function. I also have $m<n$ elements, each of which belongs to a category $\{1...i\}...
minnie's user avatar
  • 1
1 vote
1 answer
36 views

Weisfeiler-Leman Algorithm

We know that the Weisfeiler-Leman Algorithm will not always distinguish graphs that are not isomorphic but if two graphs are isomorphic are we guaranteed to get a certificate?
IsoCurious's user avatar
0 votes
1 answer
45 views

Coding the labyrinth solver

The question mathematically has been answered here: https://math.stackexchange.com/questions/4886084/guaranteed-graph-labyrinth-solving-sequence/4887473#4887473 To summarize, in an unknown strongly ...
user555076's user avatar
2 votes
1 answer
78 views

Graph labyrinth solving sequence

Starting from a vertex of an unknown, finite, strongly connected directed graph, we want to 'get out' (reach the vertex of the labyrinth called 'end'). Each vertex has two exits (edge which goes from ...
user555076's user avatar
1 vote
1 answer
75 views

How to find largest caterpillar in a tree

A caterpillar is a subgraph which consists of a path with at most four leaves (legs) attached to each node (but a node can also have no leaves). This is not the same as finding the longest path, ...
Stephen's user avatar
  • 11
0 votes
1 answer
95 views

DFS to assign guards to nodes in a tree structure

Consider a uniquely designed museum where rooms are arranged in a tree structure. Each room can have up to two child rooms connected by a path. The task is to develop an algorithm to place a minimum ...
mark's user avatar
  • 67
7 votes
3 answers
144 views

Finding a set of edges $E$ such that every $s$-$t$-path contains at least 2 edges from $E$

Given an undirected graph $G$ and two vertices $s$ and $t$, i want to find a minimum set of edges $E$ in $G$ such that every (simple) $s$-$t$-path contains at least 2 edges from $E$. Is this problem ...
tgnome's user avatar
  • 153
-1 votes
1 answer
72 views

Examples of algorithms best their class that require cyclical data structures

I remember that the Roc Lang website claimed that their choice to forbid any form of cyclic data structures prohibited their customer to implement some of the best in their class algorithms, id est ...
Delfin's user avatar
  • 99
2 votes
1 answer
45 views

Why does Hopcroft-Karp only work on bipartite graphs?

I have a simple question which I cannot answer, and it relates to this question. What I cannot answer is this: Why does a graph with bidirectional edges destroy the "bipartiteness" of the ...
Joff's user avatar
  • 155
1 vote
1 answer
63 views

Find all the induced paths with a start vertex

Let $G$ be a graph and let $v$ be a vertex. Is there a polynomial algorithm for the following operation? Operation. Find all the induced paths in $G$ with first vertex $v$. Background This problem is ...
licheng's user avatar
  • 405
1 vote
0 answers
43 views

Is there a proof for camerinis algorithm for finding a minimum bottleneck spanning tree?

Does someone know a proof for Camerinis Algorithm for finding a minimum bottleneck spanning tree? To my knowledge its the only algorithm that performs in linear time to solve this task but I cant find ...
identicon's user avatar
1 vote
1 answer
82 views

Disconnection of a directed and weighted graph

Let $G = (V, E)$ be a directed weighted graph such that all the weights on the edges are positive. In $G$, we have two nodes, $v$ and $u$, that have a path from $v$ to $u$. The question asks to find a ...
Daniel's user avatar
  • 71
0 votes
0 answers
61 views

Find an independent set in which the cumulative sum of weights is maximized

I have a weighted undirected graph G=(V,E,W), I want to find an independent set S of V, such ...
Farah Mind's user avatar
2 votes
1 answer
68 views

Covering a graph with M cliques maximizing total edges weight

I am working on a problem that involves distributing a set of N supplements across a predefined number of meals (M) in a way that maximizes the total number of positive interactions and minimizes ...
essacult's user avatar
0 votes
0 answers
104 views

Algorithm for "Clustering" a directed graph

I have a directed graph with unweighted edges between the vertices, and possible cycles. I want an algorithm that I can pass in the graph and a number N, and have it spit out a set of N clusters each ...
Li Haoyi's user avatar
1 vote
0 answers
62 views

Total combinations in DAG with upper bound on node value

There is a directed acyclic graph with M edges. There is only one component (If they were undirected edges all nodes will be reachable will from one to another). An edge from a to b means value of ...
Aryan Agarwal's user avatar
2 votes
0 answers
57 views

Are there $r$ pairwise edge-disjoint $k$-sets of internally disjoint $s$-$t$-paths? Complexity

Given an undirected graph, two vertices $s$ and $t$, and two integers $k$ and $r$, then a $k$-set of internally disjoint $s$-$t$-paths is defined to be a set of exactly $k$ $s$-$t$-paths that share no ...
tgnome's user avatar
  • 153
6 votes
0 answers
170 views

Are there $\ell$ edge-disjoint $s$-$t$-paths such that at least $k$ of them are internally disjoint? Complexity

Given an undirected graph, two vertices $s$ and $t$, and two integers $k$,$l$ - what is the complexity of finding $\ell$ edge-disjoint $s$-$t$-paths such that at least $k$ of them are pairwise ...
tgnome's user avatar
  • 153
1 vote
1 answer
60 views

Finding the pair of nodes with maximum distance in an arbitrary rooted tree

Suppose we are given an arbitrary rooted tree. We want to find two nodes that have the maximum distance among all pairs of nodes. I am looking for an algorithm with time complexity $\mathcal{O}(n)$, ...
Mason Rashford's user avatar
1 vote
1 answer
92 views

Running time of modified BFS algorithm to find shortest path in weighted DAG

While the shortest path can be calculated with $O(V+E)$ time over a weighted directed acyclic graph using topological sort, I wonder about the running time of the following BFS type algorithm I ...
wsz_fantasy's user avatar
1 vote
0 answers
25 views

CHK graph dominance algorithm proof

The algorithm developed by Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy is widely used in industry for building dominator tree, but I cannot follow the proof in the “Engineering the data ...
rand0m_scr1pt_k1dd1e's user avatar
9 votes
1 answer
166 views

Can we solve $\mathrm{MFVS} \leq 1$ in linear (or subquadratic) time?

$\mathrm{MFVS} \leq 1$ is a concise way of writing the following decision problem: Let $G = (V, E)$ be a directed graph. Is there a $v \in V$ such that every cycle in $G$ passes through $v$? (More ...
Mees de Vries's user avatar
2 votes
1 answer
61 views

Non-dominated maximal paths in a DAG

Let $D(V, A)$ be a DAG. We call a dominated path in $D$ a path $P$ such that $P$ is maximal and $\exists P^{'} \in D . (P^{'} \text{ is maximal } \wedge V(P) \subset V(P^{'}))$ that is, $P$ is a ...
Matheus Diógenes Andrade's user avatar
0 votes
0 answers
13 views

Identifying peaks at every cluster

I have a data set showing different clusters of data points and was attempting to find a way to get the peak of at every cluster. Comparing the moving average between a set of points does not work as ...
Nader's user avatar
  • 101
1 vote
0 answers
242 views

The second shortest path on a directed graph [closed]

The question asks to write an algorithm using Dijkstra's algorithm with time complexity of $\Theta(|E| \log |V|)$ that find the second shortest path between $s∈V$ and $t∈V$. The farthest I managed to ...
Daniel's user avatar
  • 71
2 votes
0 answers
63 views

Borůvka's step in linear time

I am trying to understand this Expected linear time MST algorithm, and I have a problem in the implementation of the Borůvka's step. My problem is with the removal of duplicate edges between merged ...
Nathaniel's user avatar
  • 15.7k
-2 votes
2 answers
209 views

Could this novel algorithm be qualified to be published in Nature or Science

I recently designed an algorithm for single-source shortest paths in graph structures, which can limit the number of edges as Bellman-Ford while approaching the performance of SPFA. Of course, it also ...
Shawxing Kwok's user avatar
1 vote
1 answer
31 views

Independent sets generation in a graph

Is there an algorithm that, given an undirected graph and one independent set IS1, finds an other independent set IS2 by adding and deleting vertices from the first IS1?
maliya's user avatar
  • 11
2 votes
2 answers
35 views

Algorithm question - check if there exists a path that touches A nodes exactly once and can revisit all other nodes

I am having trouble with a problem where I am given an adjacency list and a list of the nodes that must be visited exactly once to connect two nodes. What is the most efficient way of doing this? This ...
Maceo Cardinale Kwik's user avatar
1 vote
1 answer
84 views

Can Dijkstra's algorithm be used this way?

Let us say that I wanted to solve a Hamiltonian path problem by treating it as a Hamiltonian cycle(on a weighted graph). I use a TSP solver, and implement a dummy node of edge weight zero, whose ...
Johnny Upman's user avatar
1 vote
0 answers
19 views

epsilon-optimality in cycle-cancelling for min cost flow

I'm learning about the (min-mean) cycle-cancelling alg for min-cost flow in Ahuja, Magnanti, and Orlan's Network Flows book (Chapters 9 and 10). When talking about the alg, they prove this fact ...
AWhite's user avatar
  • 21
0 votes
1 answer
64 views

How to modify Dijkstra's algorithm to model the path of an electric car?

I know that Dijkstra's algorithm is used to find the shortest path between nodes in a weighted graph. And I know that this can be used to model road networks. Somebody online asked (but nobody ...
Johnny Upman's user avatar
0 votes
1 answer
134 views

Why not n^2 comparisons in the Alien Dictionary problem on leetcode?

Here's the problem statement (as given on GeeksForGeeks website): Given a sorted dictionary of an alien language having N words and k starting alphabets of standard dictionary, find the order of ...
Anurag Prasad's user avatar
2 votes
2 answers
161 views

A $O(|E||V|)$ algorithm to determine if a graph is singly connected?

In exercise 22.3-13 of CLRS (Intro to Algorithms 3rd edition), the authors provide the following problem: A directed graph $G = (V, E)$ is singly connected if the existence of a path from $u$ to $v$ ...
Hugh Mann's user avatar
0 votes
0 answers
23 views

Edge connectivity using flow network

Find an algorithm for edge connectivity in undirected graph using flow networks. Try to use $O(m)$ edges. So basically the flow network should be used as a "helper function" and the graph ...
popcorn's user avatar
  • 183
0 votes
1 answer
65 views

Optimizing Delivery Routes in a Graph-Based Network to Minimize Maximum Delivery Time

In a graph with N nodes, where each node represents a house and is labeled from 0 to N-1, an ...
maplemaple's user avatar

1
2 3 4 5
45