New answers tagged graph-theory
2
votes
Transforming finite automata with graph rewriting
I'm not sure this really answers your question, but you might be interested in this paper: https://lmcs.episciences.org/10963
It gives a graphical language of string diagrams such that:
the usual ...
0
votes
Seeking Help to Verify Algorithm for Chromatic Number in Polynomial Time
Experimentally, all i have for you is:
The Strong Color Theorem:
Most random regular graphs with degree d*d or less are d+1 colorable.
checkable is c4d9n200.
uncheckable is c5d16n80.
needs more ...
0
votes
Given a weighted DAG, is there an $O(V+E)$-time algorithm to replace each weight with the sum of its ancestor weights?
There is an algorithm work faster than $O(VE)$ in some very specific case, if you can make the digraph (after removing edges that preserve reachability of vertices) isomorphic to a minor of $P(a_1, ...
- 21
Top 50 recent answers are included