1
vote
0answers
19 views

Algorithm to lay out orthogonal connector lines without overlap

I'm drawing a graph of nodes connected by orthogonal edges with corners. The nodes are laid out on a grid, and the edges (conceptually) follow the grid lines. The paths the edges take are laid out ...
2
votes
0answers
43 views

Algorithm to find the “optimal” path in a given graph

Assume that $G=(V,E)$ is an undirected connected graph and that $H: V \to \mathbb R$ is a function that assign at each vertex $v \in V$ its height $H(v)$. Think of the pair $(G,H)$ as an energy ...
5
votes
0answers
54 views

Traveling salesman problem: can a terrible strategy beat a good one?

Until yesterday, I was under the naive impression that constructing a weighted graph where the nearest-neighbour algorithm gives the worst possible route, would have the property that any other ...
6
votes
1answer
61 views

Traveling salesman problem: a worst case scenario

For those not familiar with the problem, here is the Wiki article; it can be understood by anyone. I am in particular interested in the nearest neighbor algorithm, also known as the greedy algorithm, ...
1
vote
1answer
40 views

“Job-scheduling” problem that minimizes the number of machines

In a graph, there are points that need to be visited. For each of these points, there is a certain time interval given by its start and ...
0
votes
1answer
26 views

Minimal disjoint chains covering graph vertex set

I'm looking for references on the following problem: Given a graph $G=(V,E)$, what is the minimum number of simple, disjoint paths that span all the vertices in $V$? i.e., let $P$ be the answer to ...
2
votes
1answer
23 views

find all continuous path segments in an undirected graph

I have an undirected graph, like the following: . C . / \ . B F . / / \ . A D E The edges are: ...
0
votes
0answers
15 views

random relax based algorithm complexity

consider the follow relax based algorithm than find all the shortest paths from s: input: directed graph G = (V , E) , weight function W:E->R(real numbers), source vertex (s in V). G don't ...
0
votes
1answer
13 views

Linear-time algorithm for deciding triconnectivity?

The german site of wikipedia (Look at wikipedia k-zusammenhang) states that there are linear-time algorithms to decide whether a given undirected graph is triconnected (Deleting any two vertices ...
0
votes
0answers
15 views

Degree characterization

I have been asked in a programming contest if it is possible to construct a graph just with the degree numbers. For example, given $1,2$ the answer would be no by the handshake lemma, but that's a ...
2
votes
1answer
31 views

Preorder Traversal

For Each Preorder Traversal, we have multiple Inorder Traversal. this is True or False Conclusion? every one would help me and add some detail.
0
votes
1answer
26 views

Tarjan's algorithm to determine wheter a directed graph has a cycle

I want to know if a directed graph has a cycle; something like 1->2->3->2 ... 1->2->3->4->3... 1->1->1->1... So, I'm considering ...
0
votes
0answers
20 views

Inclusion-wise minimal feedback arc set

How is the term inclusion-wise defined? More precisely, I am trying to get a hold of what an inclusion-wise minimal feedback arc set is. Let $G = (V,E)$ be a (directed) graph. A feedback arc set $F ...
1
vote
0answers
26 views

Details of the Goldberg-Radzik algorithm for computing shortest paths

I'm trying to implement the Goldberg-Radzik algorithm, which is described in the 1993 paper "A heuristic improvement of the Bellman-Ford algorithm" by Andrew Goldberg and Tomasz Radzik (link: ...
0
votes
1answer
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 ...
0
votes
0answers
36 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 ...
1
vote
1answer
35 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 ...
0
votes
1answer
27 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 ...
0
votes
1answer
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 ...
2
votes
1answer
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?
0
votes
1answer
44 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 ...
0
votes
0answers
37 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 ...
3
votes
2answers
90 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 ...
1
vote
0answers
59 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 ...
5
votes
3answers
368 views

Recurrence with varying coefficient

Problem 1 $$ {\rm f}\left(n\right) = \frac{1}{n}\, \left[{\rm f}\left(n - 1\right)k_{0} + {\rm f}\left(n-2\right)k_{1}\right]\tag{1} $$ ( This can also be written as ${\rm Q}\left(n\right) = ...
1
vote
0answers
37 views

Maximal flow in flow-networks

I want to do the task (b),(c) and (d)in the picture above. I have done (b) correctly. For (c) I only found one (s-t) augmenting path, namely (s,1),(1,3),(3,2),(2,4),(4,t) and I only can push one ...
0
votes
0answers
47 views

Miscellaneous questions about trees

I want to know which of the following claims are true: 1) Let T be a minimal spanning tree in G for a weight function w. Then T is also a minimal spanning tree for the weight function obtained from w ...
0
votes
1answer
21 views

Proof about spanning tress in graphs

Let $G=(V,E)$ be a graph and $T_i=(V,F_i),i=1,2$ two disjoint spanning trees in $G$. Let $f_1 \in F_1$. Prove that there is $f_2\in F_2 $ such that $T:=T_1-f_1+f_2$ is a spanning tree.
1
vote
1answer
139 views

Tree Traversal - Simple Puzzle type Issue.

This is a puzzle like question,based on Fibonacci like structure of the tree. Actually it is a short question with out any complex concepts. It appears bit big,since I have added explanations with ...
1
vote
0answers
39 views

directed simple graph, all paths from node $ v_0 $ to an other node $ v $, MATLAB

consider a directed simple graph $ G=(V,E) $ with $ V=\lbrace v_0,v_1,\ldots,v_k \rbrace $ and adjacency matrix $ A=(a_{ij}) $, where $ a_{ij}=1 $ means, that there is an arc from node $ v_i $ to node ...
0
votes
1answer
34 views

Find a kernel in a directed graph.

It's a question from a sample exam I'm trying to solve but with no success yet. Let $G(V, E)$ be a directed graph. set $A \subseteq V$ is a kernel if: i. $\forall u,v\in A \implies (u, v), ...
-1
votes
1answer
50 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 ...
1
vote
3answers
37 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 ...
2
votes
1answer
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 ...
2
votes
1answer
59 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 ...
3
votes
0answers
21 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 ...
1
vote
0answers
26 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$ ...
0
votes
0answers
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 ...
0
votes
2answers
34 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.
0
votes
0answers
50 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 ...
0
votes
0answers
39 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 ...
0
votes
1answer
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)$. ...
2
votes
0answers
80 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. ...
1
vote
1answer
52 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 ...
2
votes
2answers
51 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 ...
0
votes
1answer
99 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 ...
1
vote
0answers
36 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 ...
2
votes
1answer
113 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 ...
0
votes
1answer
60 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. ...
0
votes
1answer
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 ...