Premium
Connectedness of finite distance graphs
Author(s) -
GómezPérez Domingo,
Gutierrez Jaime,
Ibeas Álvar
Publication year - 2012
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21465
Subject(s) - social connectedness , combinatorics , mathematics , graph , discrete mathematics , computer science , psychology , psychotherapist
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