Connectedness of finite distance graphs
Domingo Gómez‐Pérez, Jaime Gutiérrez, Álvar Ibeas · Networks · 2012
Abstract We describe a polynomial‐time algorithm for deciding whether a given distance graph with a finite number of vertices is connected. This problem was conjectured to be NP‐hard in Draque Penso et al. © 2012 Wiley Periodicals, Inc. NETWORKS, 2012