New answers tagged graph-algorithms
2
votes
Accepted
Escaping the cycle: Route planning in graphs with conditional logic
First, let's define/simplify the situation or condition.
We have a graph with vertices and edges.
Some edges are special, they open up (get activated) only after waiting for some time at the source.
...
- 136
5
votes
Orientations of an undirected graph
Here's an argument that falls a bit short of NP-hardness, but gives strong evidence that we shouldn't expect a polynomial time algorithm, even in the case when the graph is a star.
Theorem 1: If there'...
- 1,881
9
votes
Accepted
Orientations of an undirected graph
This problem is belongs to a family of problems referred to as Maximum (Undirected) Graph Orientation problem or similarly.
It was described for example by Medvedovsky et al. [1]
who also observed ...
- 1,934
3
votes
Graph canonization vs. NP
Indeed, not only does that seem to not be the case for GI, but one can prove a separation for other problems assuming only $\mathsf{P} \neq \mathsf{NP}$. Blass and Gurevich (SICOMP, 1984) showed that ...
- 37.8k
Top 50 recent answers are included