Metric Dimension for Gabriel Unit Disk Graphs is NP-Complete.
Stefan HoffmannEgon WankePublished in: CoRR (2013)
Keyphrases
- np complete
- polynomial time complexity
- bounded treewidth
- maximum common subgraph
- randomly generated
- minimum spanning trees
- neighborhood graph
- np hard
- satisfiability problem
- computational complexity
- constraint satisfaction problems
- phase transition
- graph theoretic
- conjunctive queries
- metric learning
- metric space
- graph matching
- graph theory
- graph databases
- similarity metric
- bipartite graph
- graph structure
- subgraph isomorphism
- np complete problems
- graph clustering
- data points
- distance function
- pspace complete
- distance metric
- graph model
- weighted graph