Efficient algorithms for network localization using cores of underlying graphs

DOI10.1016/j.tcs.2014.02.020zbMath1360.68649OpenAlexW2177765211MaRDI QIDQ742409

Takeshi Tokuyama, Meng Li, Yota Otachi

Publication date: 18 September 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.02.020

zbMATH Keywords

chordal graphconnected dominating setnetwork localizationgraph turnpike problempoint set reconstructionweighted graph embedding

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximating the tree and tour covers of a graph
• On the graph turnpike problem
• The complexity of minimizing wire lengths in VLSI layouts
• Complement reducible graphs
• Unit disk graphs
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Connected rigidity matroids and unique realizations of graphs
• Algorithmic graph theory and perfect graphs
• Upper bounds to the clique width of graphs
• Incidence matrices and interval graphs
• Parameterized complexity of Vertex Cover variants
• On graphs and rigidity of plane skeletal structures
• Polynomial Instances of the Positive Semidefinite and Euclidean Distance Matrix Completion Problems
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Algorithmic Aspects of Vertex Elimination on Graphs

This page was built for publication: Efficient algorithms for network localization using cores of underlying graphs