Login / Signup

Finding Cactus Roots in Polynomial Time.

Petr A GolovachDieter KratschDaniël PaulusmaAnthony Stewart
Published in: Theory of computing systems (2017)
A graph H is a square root of a graph G, or equivalently, G is the square of H, if G can be obtained from H by adding an edge between any two vertices in H that are of distance 2. The Square Root problem is that of deciding whether a given graph admits a square root. The problem of testing whether a graph admits a square root which belongs to some specified graph class ℋ is called the ℋ -Square Root problem. By showing boundedness of treewidth we prove that Square Root is polynomial-time solvable on some classes of graphs with small clique number and that ℋ -Square Root is polynomial-time solvable when ℋ is the class of cactuses.
Keyphrases
  • convolutional neural network
  • neural network
  • machine learning