Parameterized algorithms for finding square roots
(2014)
Journal Article
Cochefert, M., Couturier, J., Golovach, P., & Paulusma, D. (2014). Parameterized algorithms for finding square roots. Algorithmica, https://doi.org/10.1007/s00453-014-9967-4
We show that the following two problems are fixed-parameter tractable with parameter k: testing whether a connected n-vertex graph with m edges has a square root with at most n−1+k edges and testing whether such a graph has a square root with at leas... Read More about Parameterized algorithms for finding square roots.