5
Let $G = (V, E)$ be a simple graph like you described (which is unique up to isomorphism and known as the Turán graph $T(10, 5)$, by the way). Note that the maximal degree possible in a graph with $10$ vertices is $9$ and thus, for every vertex $v$ in $G$ there exists a unique vertex $w \ne v$ which is not connected to $v$ and the two vertices share a ...
3
Notice that if you allow once jumping without paying the weight cost, then the shortest path is exactly what you need.
Create 2 copies of $G: G_1,G_2$. For every edge $e=(v,u)\in G$ also add an edge $(v_1,u_2)$ between the node $v$ of $G_1$ and $u$ of $G_2$. Make those edge's weight to $0$.
Now, find a shortest path between $s_1$ and $t_2$ (using Djikstra)
2
Let $v$ be some node. then it had 8 neighbors, and there is exactly one node $u$ which is not connected to $v$. Notice that also $u$ has 8 neighbors, and thus $v$ is the only node not neighboring it.
We can partition the graph into 5 groups of 2 nodes $V_1=\{v_1,u_1\},...,V_5=\{v_5,u_5\}$, where every group's node's are not connected to each other (there is ...
2
No. If $q(x_n,y_n|T_{n-1})$ is arbitrary -- there can be an arbitrary dependence on $T_{n-1}$ -- then this requires exponential time.
Consider a tree $T_N$ that has a single root node, $N-1$ leaves, and an edge from the root to each leaf. There are $2^N$ subtrees of $T_N$, and in particular, there are $2^N$ possible values of $T_n$ that can occur in the ...
2
Your conditions are not enough. For example, the function $f(v) \equiv 0$ satisfies them, but is (usually) not the shortest distance function.
You need to strengthen your second condition.
1
It can be solved in polynomial time. For instance, you can use binary search over the weight. Given a candidate weight, delete all edges with lower weight, then find the lowest-cost path and test whether its cost is below the lower bound; that tells you whether the weight was too high or too low. Repeat until binary search converges.
1
Using the definitions from: Theoretical Computer Science: Introduction to Automata and Computability by Juraj Hromkovič.
A representation for the graph will be said to be Unambiguous if the graph can be reconstructed from that representation.
Basically, we wish to encode a general graph using boolean alphabet $\Sigma = \{0,1\}$. If we had an additional ...
1
Suppose $G = (V, E)$ is a tree with 25 vertices such that there exist some constants $c \geq 0$ and $m \geq 2$ such that $\operatorname{deg} v \equiv_m c$ for all $v$. Note that we can equivalently write $\operatorname{deg} v = a_v m + c$ for some $a_v \geq 0$.
Since $G$ is connected by definition, we get that it must have 24 edges in total, giving us
$$ \...
1
Finding a minimum s-t cut is easier than finding a minimum cut, so there is no reason to use or adapt Stoer-Wagner; instead, using a standard algorithm for finding a minimum s-t cut, such as using a network flow algorithm.
1
You can add a small value positive $\delta$ to each edge and use Dijkstra's algorithm to find the shortest path. Any $\delta < \frac{1}{V}$ will suffice.
Only top voted, non community-wiki answers of a minimum length are eligible
