Exact and approximate algorithms for computing a second Hamiltonian cycle
(2020)
Presentation / Conference Contribution
A classic result by Stockmeyer [Stockmeyer, 1974] gives a non-elementary lower bound to the emptiness problem for star-free generalized regular expressions. This result is intimately connected to the satisfiability problem for interval temporal logic... Read More about Exact and approximate algorithms for computing a second Hamiltonian cycle.