Home Issues About JGAA Instructions for Authors
 
DOI: 10.7155/jgaa.00569
Revising the Fellows-Kaschube $K_{3,3}$ Search
Vol. 25, no. 1, pp. 513-520, 2021. Concise paper.
Abstract The first algorithm to achieve linear-time performance searching for and identifying a subgraph homeomorphic to $K_{3,3}$ is due to Fellows and Kaschube. Part of the proof of correctness depends on three cases of a straddling bridge of a subgraph homeomorphic to $K_5$ in an input graph. This paper presents a missing fourth case and revises the algorithm with an additional $K_{3,3}$ homeomorph isolator for the condition corresponding to the missing case. This paper also discusses why the prior proof of correctness missed the fourth case and presents a new proof of correctness showing that there are no other missing cases.
 This work is licensed under the terms of the CC-BY license.
Submitted: June 2021.
Reviewed: September 2021.
Revised: September 2021.
Accepted: September 2021.
Final: September 2021.
Published: October 2021.
Communicated by Giuseppe Liotta
article (PDF)
BibTeX