19
FOR x := 1 TO n DO
FOR y := 1 TO n DO
FOR z := 1 TO n DO
IF E(x,y) && E(y,z) && E(z,x) THEN REJECT
ACCEPT
Each of the variables x, y and z requires $\Theta(\log \texttt{n})$ bits to store an integer between $1$ and $\texttt{n}$.
15
You don't need to first write all 3-tuples and then check, for each of them, whether it induces a triangle.
You can just enumerate the 3-tuples one at a time and reject as soon as you find one that induces a triangle. If you reach past the last 3-tuple then the graph contains no triangle and you can accept.
4
Those answers assume that all edge capacities are integers. Assuming they are, this works.
Suppose the min-cut in the original graph has total capacity $x$; then it will have total capacity $x(|E|+1)+k$ in the transformed graph, where $k$ counts the number of edges crossing that cut. Note that if you consider any cut in the original graph with larger ...
4
It turns out that the very popular textbook Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein, sneakily avoids this issue by giving a different definition of cycle in undirected vs directed graphs.
In Section B.4, it defines cycle and simple cycle as I do (they also require at least one edge), in directed graphs. In an undirected graph, ...
3
Your problem is NP-hard. There is a reduction from Independent Set to its decision version.
Consider an instance $G=(V,E)$ of Independent Set, you construct a network with vertices $\{s,t\}\cup V\cup V'$ where each vertex in $V'$ corresponds to a pair of vertices in $V$. For example, if $V=\{1,2,3\}$, then $V'=\{v_{12},v_{23},v_{13}\}$. Then we construct ...
3
Arguably two of the most definite textbooks on graph theory are Bundy & Murty (BM) (roughly 15000 citations at the time of writing) and Diestel (at least hundreds of citations).
In BM (Section 1.6), the definition of a cycle is obtained via walks and trails, i.e., a cycle is a non-empty trail in which the first and last vertex are repeated. In your ...
3
I'll go with (3)
From Bundy and Murty's Graph Theory with Applications (http://www.maths.lse.ac.uk/Personal/jozef/LTCC/Graph_Theory_Bondy_Murty.pdf), sections 1.6 "Paths and Connections" and 1.7 "Cycles":
A walk is a finite non-null sequence of alternating vertices and edges (repetition of both allowed).
If the edges of a walk are distinct then it is also ...
2
I'm afraid that this idea does not work (and I actually post this question as homework to my students, the reason being that at first glance it looks sound and complete).
Let $G(V, E)$ denote a graph with a cost function $c:e\in E\mapsto Z$, i.e., both positive and negative whole numbers, and no negative cycles. Let us assume there is an edge $e\langle v_i,...
2
This will not work. Consider
(a)-4->(b)
(a)-1->(c)
(b)-2->(d)
(c)-6->(d)
Looking for the max cost path from (a) to (d), the max heap will follow (a)-4->(b)-2->(d) and never explore the (a)-1->(c) edge.
See here for an alternative based on a topological sort.
2
Your conjecture is false. There are regular graphs with an even number of vertices yet without a 1-regular subgraph. See this question on Mathematics.
The complement of such a graph gives a counterexample to your claim that you can always add a perfect matching to increase the regularity (when the number of vertices is even).
In the bipartite case, however,...
2
The class of graphs that contain a Hamiltonian cycle is known as Hamiltonian graphs. Being Hamiltonian doesn't really imply much: a wide range of well-known graph parameters (diameter, treewidth, chromatic number, ...) can still be unbounded. At least partly, this is the reason there aren't many non-trivial subclasses of Hamiltonian graphs known.
As an ...
2
Let me tell you what Bellman-Fords is actually doing because the sentence by relaxing all edges once for every vertex in the graph is not very accurate. In Bellman-Ford you care about single-source-shortest-path. Since every path in the graph have at most $n$ nodes it has at most $n-1$ edges.
Let's say the source node is $s$, then create a table $distance[\...
2
Your post-traversal numbering of the component $C$ is incorrect. The vertex labeled as $1,6$ was assigned its post-traversal number too early; a depth-first search will also explore the vertices of $D$ before assigning the post-traversal number to this vertex.
2
The problem statement needs to be specified more precisely to be meaningful.
If I'm being pedantic, I would say that the minimum number of propositional variables is zero: you can solve the graph coloring problem (taking exponential time if necessary), then either use the formula $\text{True}$ or $\text{False}$ according to whether the graph is $C$-...
1
If the case arrives where you see the case of a node being already visited but it is the parent of your current node, you just have to check whether there is a double edge between them. How to do that depends on your data structure, but if your adjacency list is sorted it would just amount to searching for the edge and checking how often it is in there.
...
1
We first sort all edges according to their costs from small to large. Say the sorted edges are $e_1,e_2,\ldots,e_{n(n-1)}$, and the corresponding costs are $w_1\le w_2\le\cdots\le w_{n(n-1)}$. Then we find the minimal $i$ such that the graph is strongly connected only with the edges $e_1,\ldots,e_i$. Now $w_i$ is the minimal tank capacity we want.
Sorting ...
1
Use depth-first search, or breadth-first search, or any other graph search algorithm. You don't need Tarjan's algorithm.
1
You are on the right track, just keep going: what if you take a slightly larger complete graph? Specifically, what if you take a $K_{101}$?
1
The problem was considered by Kahn and Saks in their paper Balancing poset extensions. Earlier related works are Fredman, How good is the information theory bound in sorting? and Linial, The information-theoretic bound is good for merging.
Kahn and Saks showed that partially sorted lists can be sorted in $O(\log M)$, where $M$ is the number of possible ...
1
It is equivalent to the set cover problem. You can regard each vertex in the right side as a set of its neighbors in the left side. In your example, $e,f,g$ correspond respectively to the sets $\{d\},\{d\},\{a,b,c,d\}$. Now a minimum vertex cover in your problem is equivalent to a minimum set cover.
1
Let $T$ be a tree rooted at $r$ with $n > 2$ leaves, and let $\ell(u)$ denote the number of leaves in the subtree of $T$ rooted at node $u$.
Initially let $v=r$, then proceeds as follows:
If $\ell(v) \le \frac{2n}{3}$ then return $v$.
Otherwise, let $u$ be one of the children of $v$ with the largest $\ell(u)$, set $v=u$ and repeat from the first step.
...
1
The Grassfire algorithm only works on a particular kind of graph; Dijkstra's algorithm works on any graph.
Only top voted, non community-wiki answers of a minimum length are eligible
