Metric Dimension for Gabriel Unit Disk Graphs Is NP-Complete.
Stefan HoffmannEgon WankePublished in: ALGOSENSORS (2012)
Keyphrases
- np complete
- polynomial time complexity
- bounded treewidth
- maximum common subgraph
- neighborhood graph
- randomly generated
- minimum spanning trees
- np hard
- satisfiability problem
- constraint satisfaction problems
- computational complexity
- conjunctive queries
- pspace complete
- metric space
- metric learning
- graph databases
- spanning tree
- graph theoretic
- evaluation metrics
- distance metric
- graph matching
- graph theory
- graph model
- similarity metric
- graph representation
- graph kernels
- directed graph
- decision problems
- np complete problems
- phase transition