Efficient algorithms for network localization using cores of underlying graphs

DOI10.1016/J.TCS.2014.02.020zbMATH1360.68649OpenAlexW2177765211MaRDI QIDQ742409FDOQ742409

Authors Meng Li, Yota Otachi, Takeshi Tokuyama

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

network localizationchordal graphconnected dominating setgraph turnpike problempoint set reconstructionweighted graph embedding

Mathematics Subject Classification ID

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

Recommendations

• A Computational Geometry Framework for Efficient Network Localization
• scientific article; zbMATH DE number 3847184
• scientific article; zbMATH DE number 1394671
• Some new algorithms for location problems on networks
• An Axiomatic Approach to Location on Networks
• A Diffusion Approach to Network Localization
• An algorithm for locating propagation source in complex networks

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 501471 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Algorithmic Aspects of Vertex Elimination on Graphs
• Algorithmic graph theory and perfect graphs
• Approximating the tree and tour covers of a graph
• Complement reducible graphs
• Connected rigidity matroids and unique realizations of graphs
• Cutting up is hard to do: the parameterised complexity of \(k\)-cut and related problems
• Incidence matrices and interval graphs
• On graphs and rigidity of plane skeletal structures
• On the graph turnpike problem
• Parameterized complexity of Vertex Cover variants
• 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
• The complexity of minimizing wire lengths in VLSI layouts
• Unit disk graphs
• Upper bounds to the clique width of graphs

Cited in

(2)

• Algorithmic Aspects of Wireless Sensor Networks
• A Computational Geometry Framework for Efficient Network Localization

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q742409)