# All Questions

Tagged with
1,973 questions
Filter by
Sorted by
Tagged with
33 views

### There are n cities and m possible bidirectional roads and k temple. build roads with minimum cost such that each city has access to at least 1 temple

There are n cities and m possible roads and k temples. The cost of each road is given. Build ...
31 views

### Deciding whether a given flow is unique in $O(\lvert V \rvert + \lvert E \rvert)$ time

I am stuck with the following exercise: Is it possible to decide whether a given flow $f$ is a unique mamimum flow in $O(\lvert V \rvert + \lvert E \rvert)$ time? I am not sure that this is possible....
47 views

### Algorithm to find shortest distance from source to all other vertices of graph in O(m)?

My question is for (c), as I struggle to find an algorithm that can do this in O(m) time.
75 views

### Prove finding a spanning tree with no more than 50 leaves is NP-hard

This is a homework question. Consider the problem of finding if an undirected graph $G$ can have a spanning tree with no more than 50 leaves. Is this problem NP-hard? I think it is and I'm trying to ...
26 views

### Pure Directed Graph

How can a directed graph be efficiently represented in a purely functional language like Haskell? Could someone suggest relevant materials on this topic? (functional pearls perhaps?) Thanks.
29 views

### Cost of finding optimal elimination order in a planar tensor network?

Suppose we are computing a sum over $n$ factors which can be represented as a planar tensor network. What is the complexity of finding an optimal elimination order? For example, take the following ...
41 views

### Finding the shortest path with this algorithm

This is a homework question. We want to find the shortest $s$-$t$ path in an undirected weighted graph $G = (V, E)$ with capacities $c_e$ for each edge and positive weights. Let $S'$ be the set of all ...
12 views

### Is it possible to use a random seed in the form of an integer to uniformly sample items from an array in sublinear time?

For example, given an array of reservation IDs: ...
52 views

### Restore planar graph from vertex degrees

Suppose you are given a list of vertices (with known positions) and their respective degrees, find any set of non-intersecting edges that satisfies the vertex degrees. Or, in other words, connect the ...
51 views

### Why are there here at most $\vartriangle \cdot E$ paths?

I ran across this proof from the following paper: Finding and Counting Given Length Cycles But I do not understand the third line. There are at most $\vartriangle \cdot E$ such paths and they can ...
41 views

### Find nodes at k distance from given source node in an undirected cyclic graph if k<=1e9

I have encountered this problem many times. In an undirected graph, you need to get all the nodes/one node that is k distance away from the given source node (...
17 views

### Finding the minimized absolute difference of shortest paths of two different starting vertices

I am relatively new to algorithms and I hoped you can help me with the following question. The question can be summarized as follows: Given two different starting vertices, A and B, and a destination ...
169 views

### True/False: If v is a leaf in every spanning tree resulting from DFS(s), then v is a leaf in every spanning tree resulting from BFS(s)

Let $G = (V,E)$ be a connected undirected graph. Let $s \in V$ be a vertex in the graph. True/False: If $v$ is a leaf in every spanning tree resulting from DFS(s), then $v$ is a leaf in every spanning ...
37 views

23 views

### Efficient concurrent recalculation of a dynamic subset of nodes & their dependencies in a directed acyclic graph

I'm dealing with a directed acyclic graph representing calculation steps. Imagine it as something like a big excel spreadsheet, where each cell is a node in the graph. A node (cell) can have an ...
56 views

### A question about euclidean graph

I have an Euclidean graph $G$, but i should changes the weight of some edge of $G$ to $+\infty$. My problem is, after this change, $G$ remain Euclidean graph or not?
Given an undirected weighted tree with $n$ vertices, how can I design an algorithm that is $O(n^2)$ and other that is $O(n)$ for finding the longest path between two nodes in the tree (without ...