New answers tagged graph-algorithms
0
Most research regarding time complexity of dynamic reachability looks at an index structure which is updated and then queried. It would be useful to know why you want an immediate query? The link studies this idea from a descriptive complexity approach although time complexities aren't given for the queries.
https://arxiv.org/pdf/1512.05511.pdf
3
I see this question only 2.5 years after, but I think I have a relevant answer. Indeed, it is at the core of the work we have done on Fast generation of random connected graphs with prescribed degrees.
In this paper, we start with a connected graph, and perform large numbers of edge swaps in order to make it random. We however want to obtain a random ...
0
Thanks to M. kanté for pointing out further papers that studied this framework. Reading later papers that deal with vertex partioning problem framework (mostly under the name LS-VSP problems) resolved my confusion on "cofinite" condition.
Short answer: Distance-2 coloring fits in their framework. Every $\exists D_q$-problem in their framework admit ...
1
This maybe: https://papers-gamma.link/paper/32
With an open source implementation here: https://github.com/maxdan94/kClist
0
There is this quasi-linear time approximation algorithm based on HyperLogLog: https://papers-gamma.link/paper/187
4
Consider a graph on vertex set $V_1\cup V_2\cup V_3\cup V_4\cup \{a,b,c,d\}$ where $|V_1|=|V_2|=|V_3|=|V_4|=n$. The edge set $E$ is covered by $C=\{V_1\cup\{a,c\},V_2\cup\{a,d\},V_3\cup\{b,c\},V_4\cup\{b,d\},\{a,b\},\{c,d\}\}$.
When $n$ is large enough, any minimalist cover must contain the four maximum cliques $V_1\cup\{a,c\}$ and so on, so it is not hard ...
Top 50 recent answers are included
