New answers tagged graphs
2
Yes, D*-lite is a directed graph algorithm, so it works fine with asymmetric edge weights by definition.
However, note that the heuristic being admissible is not sufficient. According to the paper, it must be consistent. Based on what you described, I would guess Euclidean distance would be consistent for your graph, but we can't know for sure without ...
0
The statement is not correct. You can use your counter-example from before, and add redundant nodes to it.
Since the bellman-ford algorithm runs iterations equal to the number of nodes in the graph - you will see that nodes that are reachable from a negative cycle (but not on the negative cycle) will also get updated.
The correct statement
To clear things ...
1
Instead of "subtract", it is easier to "try to avoid".
Sort all edges first by their weights, then by whether they belong to $T$. In other words, for any two edge $e_1$ and $e_2$, $e_1$ precedes $e_2$ if and only if
$w(e_1) \lt w(e_2)$, or
$w(e_1) = w(e_2)$ and $e_1$ does not belong to $T$ and $e_2$ belongs to $T$
The above order can ...
2
There are two ways this problem can be solved. I really like these solutions.
Square Root Decomposition
Keep a set of at most O(sqrtN) "active nodes".
When you have a query of type 2, just loop through all these active nodes and add the distance between each one to the queried node. When you have a query of type 1, add the new node to the set if ...
3
The problem is still $\mathsf{NP}$-hard. For example, take a hard instance $G = (V,E)$ of the original maximum independent set problem. Add a new vertex set $V'$ to the graph such that $|V'| = |V|$ and $V'$ forms a complete graph. Also, there are no edges between $V$ and $V'$. Let the new graph be $G' = (V' \cup V, E')$ which is also a hard instance. And, $|...
0
An edge $uv$ is in some MST if and only if it is a minimum-weight edge of some cut. So we need to find a $uv$-cut with a minimum number of edges whose weight is strictly less than $w(uv)$. Once those edges are removed, $uv$ will be in some MST.
Algorithmically, any min $st$-cut algorithm, applied on the subgraph of edges of weight less than $w(uv)$, will ...
0
Create vertices
$s$, $t$
$f_1, f_2, ..., f_n$ for each of the $n$ families.
$t_1, t_2, ..., t_m$ for each of the $m$ tables.
Create edges
from $s$ to $f_i$ with capacity the size of the $i$th family.
from $f_i$ to $t_j$ with unit capacity
from $t_j$ to $t$ with the capacity the size of the table.
This ensures that each family sends at most one person to ...
0
Based on Navjot's answer, I think the complexity should be $𝑂(𝑚𝑛\times 3^s)$, because except the first step, you can only chose from 3 directions. You cannot go back to the previous position.
0
This doesn't answer your question about your particular problem, but you can find theory for a related problem involving grids by searching for "bidimensionality".
It's the idea that every graph is either low treewidth or contains a large grid minor which makes it possible to get solution in polynomial time.
See Section 3 in Beyond Planar Graphs ...
0
While implementing Johnson's algo, I think to have figure out by myself why he's exctracting the min node Id from the SCCs, during the pipeline.
Basically, Johnson's algo is:
initing a StartIndex "s" to 1, since assuming all nodes range from 1 to N
extracting a subgraph from the main graph induced by node Ids (s, s+1, ..., N)
this means the ...
2
Probably no theoretical algorithm "faster than brute-force" will be as good as using a SAT solver in practice. If you know the chromatic number already, it suffices to solve a single instance of SAT to find the coloring. Moreover, since you know the instance is always satisfiable, you can also try local search solvers such as Sparrow.
The SAT ...
0
For a Directed Graph - we keep track of the recursion stack. For an edge (u,v), if we currently are processing u, and we see that v is in the recursion stack, then we have a Cycle.
For Undirected Graph - we look construct a parent array while we are traversing with DFS. Similar situation, for an edge (u,v) while processing u, if we see that v is Visited &...
2
Given your comments that the numbers involved here are all fairly small, I recommend you use a SAT solver. There is a straightforward encoding: introduce boolean variables $x_{i,\ell}$, with the intended meaning that $x_{i,\ell}$ is true iff $\ell \in A_i$. Then all of your constraints can be translated into CNF clauses, and you can search for a satisfying ...
1
The way to tell whether there are any new developments is to look up that paper on Google Scholar, find all newer papers that cite it, and check each to see whether it reports a better result. Anyone who has an improvement will surely cite that paper.
1
I doubt there are any implementations for the algorithms you are looking for.
The problem, also known as Planar Edge Deletion, Edge Planarization, Graph Planarization, or sometimes Minimum Planarization, is NP-complete and was shown in 2007 to be fixed-parameter tractable (for every fixed number of edges you want to delete, there is a "linear time ...
1
I'm not sure where Yuval got his formula from but when trying to replicate it I got a bit lost so I will share with you what I found. You can naively calculate the number of 4 cycles using
$$\text{Tr}(A^4)=\sum_{ijkl}A_{ij}A_{jk}A_{kl}A_{li}$$
which you can read as "test if vertex $i$ is connected to vertex $j$, vertex $j$ is connected to vertex $k$ etc....
2
From my answer to a similar question:
A Delaunay edge $(x,y)$ won't be a Gabriel edge, if the set of all the possible empty disks with $x$ and $y$ on their boundaries doesn't contain the disk with minimum possible radius (which is the half-length of this edge). In other words, this will happen when the Delaunay edge $(x,y)$ doesn't intersect the segment (or ...
0
This is solvable using a product construction. You construct a new graph $G'=(V',E')$ where each vertex in $V'$ has the form $\langle v,t \rangle$, to keep track of both which vertex you're at ($v$) and the current time ($t$). Then, find a shortest path in $G'$.
To learn more about this approach, for some other examples of a product construction, see, e.g.,...
2
I will outline two solutions. Both have the same asymptotic worst-case running time, namely $O(B \cdot |E| \cdot \log (B\cdot |V|))$, but the second might be slightly more efficient in practice.
Increase the size of the graph
Create a new graph $G'$ where edges have only lengths, not costs. Each vertex is of the form $\langle v,b \rangle$ where $v \in V$ ...
1
You want to prove a false statement.
Its possible that T -{a} + {b} is not spanning tree.
Consider the below example
Lets say T1 is-
1
/ \
2 3
/ /
5 4
/
6
Lets say T2 is-
1
\
2 3
/|\ /
5 6 4
both are spanning tree but if we replace edge 1-2 in T1 with edge 2-6 in T2 then it will not be ...
6
Ah, I think I figured it out, thanks to the help from Discrete Lizard.
See the following image of a Delaunay triangulation, where I've highlighted one example where the edges would be included in DT, but not GG.
.
0
First of all, since each square consists of $4$ cells and an $n \times m$ matrix contains $nm$ cells, you can clearly fit at most $\lfloor nm/4 \rfloor$ many different cells.
If $n,m$ are both even, then you can fit $nm/4$ different square-shaped squares. In all other cases, you have to be more cunning. I won't ruin the joy of the puzzle by explaining how to ...
4
While Nathaniel's response answered my question perfectly, part of my question also asked about where to find testsets for graph isomorphism algorithms. As such, I thought I'd start a list.
http://users.cecs.anu.edu.au/~bdm/data/graphs.html
Constructing Hard Examples for Graph Isomorphism
Top 50 recent answers are included