Skip to main content
added 160 characters in body
Source Link

Note that condions 1 and 2 define a so called "unit-disk" graph. Even in this case, finding an embedding from distances is still NP-HARD. (see "A Theory of Network Localization" by Aspnes et al.) Though, as Dylan just explained, when the graph is "dense" enough to be universally rigid, then there is an efficient algorithm for (approximate) localization.

Note that condions 1 and 2 define a so called "unit-disk" graph. Even in this case, finding an embedding from distances is still NP-HARD. (see "A Theory of Network Localization" by Aspnes et al.)

Note that condions 1 and 2 define a so called "unit-disk" graph. Even in this case, finding an embedding from distances is still NP-HARD. (see "A Theory of Network Localization" by Aspnes et al.) Though, as Dylan just explained, when the graph is "dense" enough to be universally rigid, then there is an efficient algorithm for (approximate) localization.

deleted 343 characters in body
Source Link

CondionsNote that condions 1 and 2 define a so called "unit-disk" graph. Even in this case, finding an embedding from distances is still NP-HARD. (see "A Theory of Network Localization" by Aspnes et al.)

There is a stronger property than global rigidity called "universal rigidity". This means that there is only one embedding (mod Eucl) consistent with the given distances in ANY dimension. For such graphs, one can (approximately) find the embedding in polynomial time using semi-definite programming. I do not know if your graphs will have this property.

Condions 1 and 2 define a so called "unit-disk" graph. Even in this case, finding an embedding from distances is still NP-HARD. (see "A Theory of Network Localization" by Aspnes et al.)

There is a stronger property than global rigidity called "universal rigidity". This means that there is only one embedding (mod Eucl) consistent with the given distances in ANY dimension. For such graphs, one can (approximately) find the embedding in polynomial time using semi-definite programming. I do not know if your graphs will have this property.

Note that condions 1 and 2 define a so called "unit-disk" graph. Even in this case, finding an embedding from distances is still NP-HARD. (see "A Theory of Network Localization" by Aspnes et al.)

Source Link

Condions 1 and 2 define a so called "unit-disk" graph. Even in this case, finding an embedding from distances is still NP-HARD. (see "A Theory of Network Localization" by Aspnes et al.)

There is a stronger property than global rigidity called "universal rigidity". This means that there is only one embedding (mod Eucl) consistent with the given distances in ANY dimension. For such graphs, one can (approximately) find the embedding in polynomial time using semi-definite programming. I do not know if your graphs will have this property.