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
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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom