# Tagged Questions

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 ...
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 ...
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 ...
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, ...
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 ...
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 ...
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: ...
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 ...
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 ...
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 ...
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.
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 ...
20 views

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

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