Share Your Experience: Take the 2024 Developer Survey

# All Questions

Tagged with
2,246 questions
Filter by
Sorted by
Tagged with
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 ...
1 vote
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 ...
• 11
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 ...
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 ...
• 101
1 vote
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 ...
• 113
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 ...
• 405
1 vote
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 ...
• 241
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 ...
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 ...
1 vote
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 ...
• 11
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. ...
• 101
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. ...
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, ...
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?
• 1
18 views

• 183