All Questions

Tagged with
Filter by
Sorted by
Tagged with
1
vote
1answer
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 ...
2
votes
0answers
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....
1
vote
1answer
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.
2
votes
1answer
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 ...
0
votes
1answer
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.
3
votes
0answers
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 ...
0
votes
0answers
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 ...
2
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 (...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
1
vote
0answers
37 views

Exact and approximate agorithms for independent set probem in large graphs

I have a problem which could be stated as follows: Given an unweighted undirected graph $G=(V, E)$ and positive integer $k \leq |V|$, I need to find a subset of vertices $R \subseteq V$ such that $|R| ...
1
vote
1answer
92 views

Algorithm for finding MST in linear time

Are there any algorithm for finding MST of given graph $G$ in linear time? I found this paper at this link But I can't understand it running time is linear or not.
1
vote
1answer
46 views

Find MST after decrease weight of some edges

We are given an undirected weighted graph $G=(V,E)$ that contains at most $2n$ edges, as well as an MST of $G$. If we decrease the weight of exactly $n$ edges, is it possible to compute an MST of $G$ ...
1
vote
0answers
26 views

Linear programming and network flow

I would like some hint in this homework question. I have to write the max-flow problem (with souce $s$ and sink $t$) as a linear program. I have to do this by defining variables on each $s - t$ path, ...
1
vote
0answers
34 views

Finding a path that passes through a given vertex

This is a homework question. Let $G = (V, E)$ be an undirected graph. Let $u, v, w \in V$, find a path from $u$ to $w$ that passes through $v$. I know that I can solve this by running BFS on $u$ and ...
1
vote
0answers
56 views

How to find the shortest path that visits all nodes of a non-complete graph (repeating nodes allowed)?

Let $G$ be a non-complete weighted (only positive weights) undirected connected graph. I'm trying to find a path such that it visits all nodes at least once (repeating nodes is allowed), and it's the ...
1
vote
1answer
30 views

Linear deterministic algorithm for finding spanning tree T with minimal maximum edge

Given an undirected connected graph $G = (V, E)$ with weights $w : $E → $R$$^+$, define for a spanning tree T the value $λ$(T) = $max_e$∈$T${w(e)} (the maximal edge weight in T ). I need to find a ...
3
votes
1answer
49 views

N points with maximum sum distance

Given a distance matrix for 50,000 points, how do I select $N$ points so that the sum of all distances between the $N$ points is maximized? $N$ could be as high as 100. To calculate the sum of ...
0
votes
0answers
30 views

Dijkstra algorithm for DAG

Assuming we have a K-Partite DAG (edges are directed from one level to the next) with edge weights either 0, 1 or 2. We are looking for the shortest path between a node from group 0 to group k-1 (path ...
3
votes
1answer
203 views

Finding the most profitable path

I will be working on a project soon and as I'm clearly not a star (see what I did?) in CS, I'm not sure what to think about this. To put it simply, the problem is the following: We want to go from ...
0
votes
0answers
31 views

Similarity between two sequences

I have two sequences whose similarity I want to measure. Lets say sequence 1 is: abcd and sequence 2 is: badc. These sequences are always of the same length and they contain exactly the same non-...
1
vote
0answers
20 views

Determining whether DAG is semi-connected

I have been asked to write an algorithm which determine whether a DAG is semi-connected. (Recall that a DAG is semi-connected if for any pair of vertices $x,y$, there is either a path from $x$ to $y$ ...
0
votes
0answers
35 views

An approximation algorithm for partitioning metric completed graph

Given complete metric weighted graph $G=(V,E)$ with $n$ vertices. Are there an algorithm that partition $G$ into to disjoint part $(C_1,C_2)$ that sum of heaviest edge $e\in C_1$ and heaviest edge $e'...
3
votes
1answer
50 views

Weighted maximum match for intervals

Say I have two sets of intervals sorted by time $I_1=[(x_1, y_1),... (x_n, y_n)]$ and $I_2 = [(a_1, b_1)... (a_m, b_m)]$. where $x, y, a, b$ are times in seconds. None of the intervals within $I_1$ ...
1
vote
1answer
30 views

Assigning balls to bins with constraints

Let $S= \{ b_{11}, b_{12}, b_{21}, b_{22}, b_{31}, b_{32},\dots, b_{n1}, b_{n2} \}$ be a set of $2n$ balls grouped in $n$ pairs, and $T = \{ B_1, B_2, \dots, B_m\}$ be a set of $m$ bins with ...
0
votes
0answers
147 views

Problems/properties of dynamic graphs with strong lower bounds

I know from [1] that the lower bound for the maximum hitting time of simple random walk on a dynamic graph is $\Omega(2^n)$. Smoothed analysis has been applied to the maximum hitting time [3] and ...
1
vote
1answer
75 views

How should i face the cluster editing problem?

The mentioned problem: Cluster Editing Problem. I need to code this problem but i can't understand the algorithm behind it, even when i try to search for resources about graphs into the web; can ...
2
votes
1answer
46 views

Upper-bounding the out-going degree of a graph

Given a graph $G=(V,E)$, I'm looking for a way to orient its edges in a way that will bound its out degree. For example, I can bound the graph's out-degree by $\approx 2\cdot a(G)$, where $a(G)$ is $G$...
2
votes
0answers
45 views

Variation of the gas station problem

Consider an acylicic directed weighted graph in which the nodes represent cities and the weights represent the amount of fuel a car spends when going through that edge. At each city $u$ the car ...
1
vote
1answer
52 views

Traversing a directed graph with negative weights

Let $G = (V, E)$ be a directed graph with negative edge weights and no cycles, and $L:V \to \mathbb [0, \infty[$ be a function defined over this graph. This graph represents all possible paths a ...
1
vote
1answer
40 views

Algorithm to find the path with minimum bending points on a square grid board

Let's suppose we have a square grid board like the one shown in the picture below: I'm wondering how I can find the path with minimum number of "bending" points (like the ones shown in red) ...
1
vote
1answer
24 views

Given a source and destination, find the path with minimum stress level in a Graph

I faced this problem in a hiring challenge which is now over. I wrote a solution for the problem but at that time the judge gave me wrong answer. Afterwords I thought about the solution but couldn't ...
2
votes
1answer
40 views

Proof that any algorithm who builds a spanning tree using Cut and Cycle properties is an MST

The Kleinberg and Tardos Algorithm makes the following claim without proof: Any algorithm that builds a spanning tree by repeatedly including edges when justified by the Cut Property and deleting ...
5
votes
1answer
134 views

Is classical algorithms a dead research field?

I'm starting my masters in CS soon, and I have to decide on a general research topic. In my undergraduate studies, I've enjoyed courses regarding data structures and algorithms the most. I'm also an ...
1
vote
1answer
20 views

Lower bound for worst case running time for k-clique problem

A naive algorithm for determining whether a graph with $|V|$ vertices has a clique of size $k$ is to list all $k$-subsets of $V$, and check each one to see whether it forms a clique. Why is the ...
0
votes
0answers
27 views

Removing and adding edges from spanning tree

Let $T_1$ and $T_2$ be two spanning trees. If $a$ is an edge in $T_1$ that is not in $T_2$, and $b$ is an edge in $T_2$ that is no in $T_1$. I want to prove that $T_1 - \{ a\} + \{ b\}$ is a spanning ...
0
votes
0answers
114 views

Approximating the number of triangles using $\ell_0$ sampling

How do you solve the following question, from this assignment? Question 2. Consider a stream that consists of the $m$ (distinct) edges of a graph on $n$ nodes. Let $T$ be the number of triangles in ...
0
votes
1answer
103 views

Time-varying edge cost Minimum Spaning Tree

I am having a hard time wrapping my head around the time-varying edge cost of this question : Suppose we have a connected graph $G = (V, E)$. Each edge e now has a time-varying edge cost given by a ...
4
votes
0answers
54 views

Finding the smallest distance between a point and a set of points

I have a GPS dataset that corresponds to a route taken by a vehicle in a day. It consist of a set of coordinates. Then say I have a coordinate and I want to know how close this coordinate is to this ...
1
vote
1answer
49 views

Why we need topological ordering for finding shortest paths

This question is just for discussing algorithms please and not for proposing algorithms. I saw very similar post to mine, but still the answer explains definitions online for topological ordering. ...
3
votes
1answer
43 views

Comparing different versions of Steiner Connected Component Subgraph problem

Problem 1 Let $G(V,E)$ be a directed graph. Let $T \subseteq V$ be a subset of vertices called terminals. Find a subgraph $H$ of $G$, such that $T \subseteq V(H)$, $H$ is a strongly connected ...
1
vote
1answer
42 views

Detecting odd cycle using mod operator and breadth first search algorithm

If we want to detect and odd cycle if an undirected graph $G=<V,E>$. Suppose we run BFS algorithm from CLRS book as follows, Q: Now my question is suppose we have the following graphs: The ...
0
votes
0answers
23 views

Prove that $d[v_r] \le d[v_1] +1 ~and~ d[v_i] \le d[v_{i+1}], i=1,2, \cdots, r-1$ on queue $Q$ based on BFS algorithm

Given the following lemma first: Lemma 1: Let $G=<V,E>$ be a directed or undirected graph, and let $s \in V$ be an arbitrary vertex. Then, for any edge $(u,v) \in E$, $$\lambda(s,v) \le \lambda(...
2
votes
0answers
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 ...
0
votes
1answer
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?
3
votes
2answers
83 views

Check if there is a subset of coordinates where each coordinate in the subset is diagonal to each other

Problem Statement Given a list of XY coordinates of length N ( e.g. [(1,2),(3,4)] ) check if there is a subset of coordinates of length S where each coordinate of ...
0
votes
0answers
41 views

Longest path in a tree [duplicate]

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 ...

1
2 3 4 5
40