Searching forK3,3in linear time
Michael R. Fellows, Paul A. Kaschube · Linear and Multilinear Algebra · 1991
It is shown that the search version of the subgraph homeomorphism problem for K 3,3 can be solved in time linear in the number of vertices of an arbitrary graph. This improves upon a previous result of Asano [1], who described a linear-time algorithm for the decision version of the problem and a quadratic-time algorithm for the search problem.