# Tagged Questions

22 views

### Maximal-size set of disjoint edges

Inspired by a "real-world" puzzle (actually, an unimportant aspect of a free-to-play game someone I know is playing)... Given an arbitrary (finite) undirected graph, I want to compute a ...
26 views

### k- maximally link disjoint paths and equations

This problem is NP-complete and also discussed to some extent in Graph problems which are NP-Complete on directed graphs but polynomial on undirected graphs from the level of my reading from various ...
31 views

### can dijkstra's algorithm be applied as it is for undirected graph

I am wondering why can't Dijkstra's algorithm be applied as it is for undirected graphs. I mean instead of adding 2 directed edges to make it equivalent to a directed graph , why wouldn't it work if ...
26 views

### How to check if a 2D mesh is connected

I'm trying to optimize structures by using FEM and genetic algorithms (GA), the FEM solver is a commercial one, and I'm programming the GA. Something like this. My first approach is simple, just ...
44 views

### Algorithm for finding contradictions in a directed graph that represents implications

I need an algorithm that does this: For a directed graph where nodes represent boolean values and edges represent implication (implies TRUE and implies FALSE): If (arc exists between any ...
20 views

### Non probabilistic algorithm for min-cut problem?

I know about Karger's algorithm and its variations, all of them being probabilistic. Is there non-trivial (i.e. non-brutefoce) deterministic algorithm for mincut problem?
39 views

### Betweenness Centrality: How Long Does Mathematica Take?

A simple maths problem. If I have a disk of unit radius and place within it $N$ nodes such that the node density $\rho$ is given by $$\rho=\frac{N}{\pi R^{2}}=\frac{N}{\pi}$$ then connect each node ...
33 views

### Number of unique ways to edge-label a complete graph with $k$ distinct labels.

Given $k$ distinct labels, how many unique ways to label the edges of a complete graph with $n$ nodes (nodes are not labeled). For example, to label a complete graph with 3 nodes using 4 distinct ...
89 views

### Fibonaaci Recurrence

This is an interesting question where we are trying to solve another recursion which has same tree structure as the given recursion and also has term similarities Given Data in question ...
58 views

### Sparse matrix algorithms involving data-driven or random access / walk

I am looking for some well-known algorithms in which sparse matrix elements are accessed in a non-structured way, i.e. row/column depends on a value of another (sparse) matrix/vector element or some ...
364 views

48 views

### Friends meeting at point

N friends live in different houses spread across the city.There are M roads connecting the houses. The road network formed is connected and does not contain self loops and multiple roads between same ...
33 views

### Find an odd-length cycle in an undirected graph.

I have an exam next week and I found a question that I have difficults to solve: Given the following: Input: Simple undirected graph $G(V, E)$. Output: Find an odd-length cycle in $G$ or ...
44 views

### Partition of graph with maximal score

Let $G=(V,E)$ be an undirected graph. Suppose that we partition the nodes into groups $C_1,C_2,\ldots,C_k$. The score of group $C_i$ is $E(C_i)/n(C_i)$, where $E(C_i)$ is the number of edges within ...
48 views

### Checking connectivity of adjacency matrix

What do you think is the most efficient algorithm for checking whether a graph represented by an adjacency matrix is connected? In my case I'm also given the weights of each edge. There is another ...
19 views

### Connected graph where edge costs depend on a parameter $t$. Find the $t^*$ which gives the minimum cost minimum spanning tree.

The set-up: Let $G=(\,V,\,E\,)$ be a connected graph. Associated with every edge $e\in E$ is a cost/weight function $f_e(t) = a_e t^2 + b_e t + c_e$, where $a_e>0$. For a fixed $t$ we can define ...
25 views

### Splitting a graph into two isomorphic parts

Say a graph $G$ has $2n$ vertices. I'd like to know if I can partition the vertices of $G$ into two parts $X$ and $Y$ such that $G[X]$ is isomorphic to $G[Y]$ ($G[S]$ denotes the subgraph of $G$ ...
58 views

### 2 player team knowing maximum moves

Given a list of N players who are to play a game. Each of them are either well versed in a move or they are not. Find out the maximum number of moves a 2-player team can know. And also find out how ...
33 views

### In Dijkstra algorithm, it takes the source, what about the sink?

I'm studying the Dijkstra algorithm, but in my book, the algorithm takes as input only the graph and the source. Why it doesn't ask for the destination vertex? How can it work? Thanks a lot.
38 views

### Smart Travelling Agent Problem

Smart travel agent, Mr. X's is to show a group of tourists a distant city. As in all countries, certain pairs of cities are connected by two-way roads. Each pair of neighboring cities has a bus ...
38 views

### What is exactly a DFS tree?

Here's a question: Claim: Every time we run the DFS algorithm on the following graph, The DFS tree will be lanyard (?) True \ False, Explanation: I Googled but I'm not pretty ...
25 views

### Find Maximum-Matching in a tree $T(V, E)$ in $O(V)$

It's a question from a previous exam that I'm trying to solve with no success. Suggest a Dynamic-Programming algorithm for the following problem: Input: indirected tree $T(V, E)$. ...
79 views

### Building Minimum warehouses

A big international retailer is setting up shop in India and plans to open stores in N towns (3 ≤ N ≤ 1000), denoted by 1, 2, . . . , N. There are direct routes connecting M pairs among these towns. ...
50 views

### The problem of finding the shortest path/route/tour that visits every vertex at least once

I have a non-directed non-weighted graph and I want to find the shortest path/route/tour (I don't know which is the correct definition) that visits every vertex at least once. Is there an algorithm ...
40 views

### Forming a simple polygon from the extrusion of a polygonal chain

Let's say I have a set of vertices connected by edges to form a polygonal chain. Each vertex may be shared by a number of edges to form various sub-chains. An example is shown below. Each edge has ...
47 views

### Find all “critical nodes” in a graph

Say there is a graph in which every node is connected to every other by some path. How would i find the particular nodes, which if removed would lead to some of the nodes NOT being connected to all ...
35 views

### Using red/blue algorithm on graph with zero cycle

I have a graph where I am trying to find minimum spanning tree using the red rule, blue rule approach. Now the graph is a directed graph and it has a zero cost cycle near the terminal point. In fact ...
110 views

### Counting triplets with red edges in each pair

Given a tree having N vertices and N-1 edges where each edges is having one of either red(r) or black(b) color. I need to find how many triplets(a,b,c) of vertices are there, such that on the path ...
50 views

### Bipartite graph set cover

I don't know much about graph theory so I would need to know if the following problem has a positive answer or a reference. There is an undirected bipartite graph G with the two vertex sets V1, V2. ...
37 views

### Find $k$ non-disrupting paths from $s$ to $t$

Given the bidirectional graph $G = (V, E)$ where $V$ = set of Vertices, $E$ = set of Edges; given source node $s$ and destination node $t$. Let $A_i$ ($i = 1, 2,\ldots l$) be the subset of vertices ...
36 views

### Dijkstra Algorithm proof

I was studying the proof of correctness of the Dijkstra's algorithm . In the above slide , $d(u)$ is the shortest path length to explored $u$ and $$\pi(v) = \min_{ e\ =\ u,v:u \in S}d(u) + l_e$$ and ...
24 views

### Algorithm to check if a graph has exactly one perfect matching

What is an algorithm to check if a general graph has exactly 1 perfect matching? Or an algorithm to check whether a graph has more than 1 perfect matching?
38 views

### Check if there's a cycle in an undirected graph

I'm trying to find an algorithms that checks if there's a cycle in a given undirected graph G=(V,E). But I didn't succeed. Can anyone give me such an algorithm?
20 views

### Minimum k-spanning tree including a given node

Given a Graph (V, E), it is very easy to find the minimum spanning tree using Kruskal's Algorithm. A k-minimum spanning tree is restricted to k nodes, and finding it is actually NP-hard. However, ...
72 views

### Shortest path between wikipedia articles

I'm trying to figure out whether it is possible (and if so how) to find the shortest path inside a network from one node to another. I know that there are different possible algorithms to do that the ...
63 views

### 3-pass counting triangles algorithm

Hei guys, I need some hints on Counting subgraphs in data streams. Consider this 3-pass counting triangles algorithm: 1st Pass: count the number of edges |E| in the stream 2nd Pass: sample ...
115 views

### Bipartite graph matching like problem.

Let $A=\{a_1,a_2, ..., a_n \}$ and $B=\{b_1,...,b_m\}$ be finite sets. Also $A_1,...,A_k\subset A$ are covering of $A$ and $B_1,...,B_t\subset B$ are covering of $B$. Let $V$ be a set of pairs of ...
31 views

### Maximum number of induced $P_3$ in a $P_4$-free graph

Say I have a graph $G$ on $n$ vertices that is $P_4$-free (it has no induced paths of length 4). These are known as cographs. Note that $G$ might not be connected. I'd like to list the induced $P_3$ ...
36 views

### O(m) all-pairs shortest paths algorithm for directed acylical graph

An exercise I'm working on asks me to devise an $O(m)$ algorithm for the all-pairs shortest paths of the graph $G = (V, A)$, where $(v_i, v_j) \in A$ implies $i < j$. I'm wondering whether this is ...
26 views

### Computer program for decomposing a graph into subgraphs?

Obviously there are programs out there that can find perfect matchings. I am interested in finding out if there is a program that can, for instance, tell when graphs like the cube graph $Q_n$, has ...
59 views

### Dijkstra's Algorithm- Two equal weights, one leads to a shorter path. What to do?

I am confused about this situation that happened to me as I was trying to solve a shortest path problem using Dijkstra's Algorithm. '$s$' is the starting point and '$t$' is finish. When I reach to ...
27 views

### Independent Sets that are Odd Covers

I am interested in a certain type of independent set I call an "odd cover". A set of vertices is independent if no two vertices in the set are connected with an edge. A set of vertices is an "odd ...
### Prove choosing $\lceil\frac{V}{2}\rceil$ vertices accounts for at least $\frac{3}{4}$ of edges
Give a polynomial-time algorithm that finds $\lceil\frac{V}{2}\rceil$ vertices that collectively account for at least $\frac{3}{4}$ of the edges in an arbitrary undirected graph. The algorithm I have ...