Search results for "spanners"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
20	Sariel Har-Peled, Manor Mendel	Fast construction of nets in low dimensional metrics, and their applications.	SCG	2005	DBLP DOI BibTeX RDF	approximate distance oracle, compact representation scheme, well separated pair decomposition, spanners, approximate nearest neighbor search, doubling metrics
20	Martin Burkhart, Pascal von Rickenbach, Roger Wattenhofer, Aaron Zollinger	Does topology control reduce interference?	MobiHoc	2004	DBLP DOI BibTeX RDF	network spanners, ad-hoc networks, interference, topology control, network connectivity
20	Lujun Jia, Rajmohan Rajaraman, Christian Scheideler	On local algorithms for topology control and routing in ad hoc networks.	SPAA	2003	DBLP DOI BibTeX RDF	mobile computing and communication, routing, distributed algorithms, competitive analysis, ad hoc wireless networks, spanners, adversarial model
20	Yehuda Hassin, David Peleg	Sparse communication networks and efficient routing in the plane.	Distributed Comput.	2001	DBLP DOI BibTeX RDF	Communication networks, Routing schemes, Geometric spanners
20	Baruch Awerbuch, Bonnie Berger, Lenore Cowen, David Peleg	Near-Linear Cost Sequential and Distribured Constructions of Sparse Neighborhood Covers	FOCS	1993	DBLP DOI BibTeX RDF	near-linear cost sequential constructions, distributed constructions, sparse neighborhood covers, dynamic approximate shortest paths, distance-preserving graph spanners, network synchronizer constructions, adaptive routing, sequential algorithms, breadth-first-search, network decompositions
20	Baruch Awerbuch, David Peleg	Sparse Partitions (Extended Abstract)	FOCS	1990	DBLP DOI BibTeX RDF	sparse partitions, polynomial routing, online tracking, locality-preserving representations, graph-theoretic structures, tree covers, diameter-based separators, protocols, clustering algorithms, covers, regional matchings, network applications, decomposition techniques, arbitrary networks, sparse spanners
15	Sujoy Bhore, Arnold Filtser, Hadi Khodabandeh, Csaba D. Tóth	Online Spanners in Metric Spaces.	SIAM J. Discret. Math.	2024	DBLP DOI BibTeX RDF
15	Abolfazl Poureidi, Mohammad Farshi	On algorithmic complexity of imprecise spanners.	Comput. Geom.	2024	DBLP DOI BibTeX RDF
15	Davide Bilò, Gianlorenzo D'Angelo, Luciano Gualà, Stefano Leucci 0001, Mirko Rossi	Blackout-tolerant temporal spanners.	J. Comput. Syst. Sci.	2024	DBLP DOI BibTeX RDF
15	Hadi Khodabandeh, David Eppstein	Maintaining Light Spanners via Minimal Updates.	CoRR	2024	DBLP DOI BibTeX RDF
15	Sebastian Angrick, Ben Bals, Tobias Friedrich 0001, Hans Gawendowicz, Niko Hastrich, Nicolas Klodt, Pascal Lenzner, Jonas Schmidt 0002, George Skretas, Armin Wells	Towards Linear Spanners in All Temporal Cliques.	CoRR	2024	DBLP DOI BibTeX RDF
15	Sarita de Berg, Tim Ophelders, Irene Parada, Frank Staals, Jules Wulms	The Complexity of Geodesic Spanners using Steiner Points.	CoRR	2024	DBLP DOI BibTeX RDF
15	Greg Bodwin, Bernhard Haeupler, Merav Parter	Fault-Tolerant Spanners against Bounded-Degree Edge Failures: Linearly More Faults, Almost For Free.	SODA	2024	DBLP DOI BibTeX RDF
15	Alina Harbuzova, Ce Jin 0001, Virginia Vassilevska Williams, Zixuan Xu	Improved Roundtrip Spanners, Emulators, and Directed Girth Approximation.	SODA	2024	DBLP DOI BibTeX RDF
15	Asaf Petruschka, Shay Sapir, Elad Tzalik	Color Fault-Tolerant Spanners.	ITCS	2024	DBLP DOI BibTeX RDF
15	Ofer Neiman, Idan Shabat	On the Size Overhead of Pairwise Spanners.	ITCS	2024	DBLP DOI BibTeX RDF
15	Kyungjin Cho, Jihun Shin, Eunjin Oh 0001	Approximate Distance Oracle for Fault-Tolerant Geometric Spanners.	AAAI	2024	DBLP DOI BibTeX RDF
15	Antoine Amarilli, Benny Kimelfeld, Sébastien Labbé 0003, Stefan Mengel	Skyline Operators for Document Spanners.	ICDT	2024	DBLP DOI BibTeX RDF
15	Greg Bodwin	An Alternate Proof of Near-Optimal Light Spanners.	SOSA	2024	DBLP DOI BibTeX RDF
15	Markus L. Schmid	The Information Extraction Framework of Document Spanners - A Very Informal Survey.	SOFSEM	2024	DBLP DOI BibTeX RDF
15	Sariel Har-Peled, Manor Mendel, Dániel Oláh	Reliable Spanners for Metric Spaces.	ACM Trans. Algorithms	2023	DBLP DOI BibTeX RDF
15	Michael Elkin, Yuval Gitlitz, Ofer Neiman	Improved weighted additive spanners.	Distributed Comput.	2023	DBLP DOI BibTeX RDF
15	William S. Evans, Lucca Morais de Arruda Siaudzionis	On path-greedy geometric spanners.	Comput. Geom.	2023	DBLP DOI BibTeX RDF
15	Frederick Anderson, Anirban Ghosh 0002, Matthew Graham, Lucas Mougeot, David Wisnosky	Bounded-Degree Plane Geometric Spanners in Practice.	ACM J. Exp. Algorithmics	2023	DBLP DOI BibTeX RDF
15	Mengshi Li, Feihu Huang, Jian Peng 0002	Finding reinforced structural hole spanners in social networks via node embedding.	Intell. Data Anal.	2023	DBLP DOI BibTeX RDF
15	Tsuri Farhana, Matthew J. Katz	Spanners under the Hausdorff and Fréchet Distances.	CoRR	2023	DBLP DOI BibTeX RDF
15	Greg Bodwin, Bernhard Haeupler, Merav Parter	Fault-Tolerant Spanners against Bounded-Degree Edge Failures: Linearly More Faults, Almost For Free.	CoRR	2023	DBLP DOI BibTeX RDF
15	Alexandr Andoni, Hengjie Zhang	Sub-quadratic (1+\eps)-approximate Euclidean Spanners, with Applications.	CoRR	2023	DBLP DOI BibTeX RDF
15	Elena Grigorescu, Nithish Kumar, Young-San Lin	Approximation Algorithms for Directed Weighted Spanners.	CoRR	2023	DBLP DOI BibTeX RDF
15	Sarita de Berg, Marc J. van Kreveld, Frank Staals	The Complexity of Geodesic Spanners.	CoRR	2023	DBLP DOI BibTeX RDF
15	Arnold Filtser, Yuval Gitlitz, Ofer Neiman	Light, Reliable Spanners.	CoRR	2023	DBLP DOI BibTeX RDF
15	Timothy M. Chan, Zhengcheng Huang	Constant-Hop Spanners for More Geometric Intersection Graphs, with Even Smaller Size.	CoRR	2023	DBLP DOI BibTeX RDF
15	Greg Bodwin	An Alternate Proof of Near-Optimal Light Spanners.	CoRR	2023	DBLP DOI BibTeX RDF
15	Antoine Amarilli, Benny Kimelfeld, Sébastien Labbé 0003, Stefan Mengel	Skyline Operators for Document Spanners.	CoRR	2023	DBLP DOI BibTeX RDF
15	Kevin Buchin, Joachim Gudmundsson, Antonia Kalb, Aleksandr Popov 0001, Carolin Rehs, André van Renssen, Sampson Wong	Oriented Spanners.	CoRR	2023	DBLP DOI BibTeX RDF
15	Hung Le 0001, Shay Solomon, Cuong Than	Optimal Fault-Tolerant Spanners in Euclidean and Doubling Metrics: Breaking the Ω(log n) Lightness Barrier.	CoRR	2023	DBLP DOI BibTeX RDF
15	Diksha Goel, Hong Shen 0001, Hui Tian 0001, Mingyu Guo	Discovering Top-k Structural Hole Spanners in Dynamic Networks.	CoRR	2023	DBLP DOI BibTeX RDF
15	Aditya Bhaskara, Sepideh Mahabadi, Ali Vakilian	Tight Bounds for Volumetric Spanners and Applications.	CoRR	2023	DBLP DOI BibTeX RDF
15	Bernhard Haeupler, D. Ellis Hershkowitz, Zihan Tan	Parallel Greedy Spanners.	CoRR	2023	DBLP DOI BibTeX RDF
15	Alina Harbuzova, Ce Jin 0001, Virginia Vassilevska Williams, Zixuan Xu	Improved Roundtrip Spanners, Emulators, and Directed Girth Approximation.	CoRR	2023	DBLP DOI BibTeX RDF
15	Prosenjit Bose, Tyler Tuttle	Routing on Heavy Path WSPD Spanners.	CoRR	2023	DBLP DOI BibTeX RDF
15	Kyungjin Cho, Jihun Shin, Eunjin Oh 0001	Approximate Distance and Shortest-Path Oracles for Fault-Tolerant Geometric Spanners.	CoRR	2023	DBLP DOI BibTeX RDF
15	Diksha Goel, Hong Shen 0001, Hui Tian 0001, Mingyu Guo	Effective Graph-Neural-Network based Models for Discovering Structural Hole Spanners in Large-Scale and Diverse Networks.	CoRR	2023	DBLP DOI BibTeX RDF
15	Asaf Petruschka, Shay Sapir, Elad Tzalik	Color Fault-Tolerant Spanners.	CoRR	2023	DBLP DOI BibTeX RDF
15	Zihan Tan, Tianyi Zhang 0008	Almost-Optimal Sublinear Additive Spanners.	CoRR	2023	DBLP DOI BibTeX RDF
15	Ofer Neiman, Idan Shabat	On the Size Overhead of Pairwise Spanners.	CoRR	2023	DBLP DOI BibTeX RDF
15	R. Inkulu, Apurv Singh	Vertex fault-tolerant spanners for weighted points in polygonal domains.	Discret. Math. Algorithms Appl.	2023	DBLP DOI BibTeX RDF
15	Markus Wallinger, Daniel Archambault, David Auber, Martin Nöllenburg, Jaakko Peltonen	Faster Edge-Path Bundling through Graph Spanners.	Comput. Graph. Forum	2023	DBLP DOI BibTeX RDF
15	Alan M. Frieze, Wesley Pegden	Spanners in randomly weighted graphs: Euclidean case.	J. Graph Theory	2023	DBLP DOI BibTeX RDF
15	Mohsen Ghaffari 0001, Christoph Grunau, Bernhard Haeupler, Saeed Ilchi, Václav Rozhon	Improved Distributed Network Decomposition, Hitting Sets, and Spanners, via Derandomization.	SODA	2023	DBLP DOI BibTeX RDF
15	Hung Le 0001, Shay Solomon, Cuong Than	Optimal Fault-Tolerant Spanners in Euclidean and Doubling Metrics: Breaking the Ω (log n) Lightness Barrier.	FOCS	2023	DBLP DOI BibTeX RDF
15	Alexandr Andoni, Hengjie Zhang	Sub-quadratic (1+ϵ)-approximate Euclidean Spanners, with Applications.	FOCS	2023	DBLP DOI BibTeX RDF
15	Kevin Buchin, Joachim Gudmundsson, Antonia Kalb, Aleksandr Popov 0001, Carolin Rehs, André van Renssen, Sampson Wong	Oriented Spanners.	ESA	2023	DBLP DOI BibTeX RDF
15	Hung Le 0001, Lazar Milenkovic, Shay Solomon	Sparse Euclidean Spanners with Optimal Diameter: A General and Robust Lower Bound via a Concave Inverse-Ackermann Function.	SoCG	2023	DBLP DOI BibTeX RDF
15	Arnold Filtser	Labeled Nearest Neighbor Search and Metric Spanners via Locality Sensitive Orderings.	SoCG	2023	DBLP DOI BibTeX RDF
15	Sarita de Berg, Marc J. van Kreveld, Frank Staals	The Complexity of Geodesic Spanners.	SoCG	2023	DBLP DOI BibTeX RDF
15	Timothy M. Chan, Zhengcheng Huang	Constant-Hop Spanners for More Geometric Intersection Graphs, with Even Smaller Size.	SoCG	2023	DBLP DOI BibTeX RDF
15	Maulein Pathak, Yogish Sabharwal, Neelima Gupta	Scalable algorithms for compact spanners on real world graphs.	ICS	2023	DBLP DOI BibTeX RDF
15	Aditya Bhaskara, Sepideh Mahabadi, Ali Vakilian	Tight Bounds for Volumetric Spanners and Applications.	NeurIPS	2023	DBLP BibTeX RDF
15	Hung Le 0001, Shay Solomon	A Unified Framework for Light Spanners.	STOC	2023	DBLP DOI BibTeX RDF
15	Zihan Tan, Tianyi Zhang 0008	Almost-Optimal Sublinear Additive Spanners.	STOC	2023	DBLP DOI BibTeX RDF
15	Elena Grigorescu, Nithish Kumar, Young-San Lin	Approximation Algorithms for Directed Weighted Spanners.	APPROX/RANDOM	2023	DBLP DOI BibTeX RDF
15	Sepehr Assadi, Michael Kapralov, Huacheng Yu	On Constructing Spanners from Random Gaussian Projections.	APPROX/RANDOM	2023	DBLP DOI BibTeX RDF
15	Rubi Arviv, Lily Chung, Reut Levi, Edward Pyne	Improved Local Computation Algorithms for Constructing Spanners.	APPROX/RANDOM	2023	DBLP DOI BibTeX RDF
15	Sergey Bereg, Yuya Higashikawa, Naoki Katoh, Junichi Teruyama, Yuki Tokuni, Binhai Zhu	Red-Black Spanners for Mixed-Charging Vehicular Networks.	COCOON (1)	2023	DBLP DOI BibTeX RDF
15	Eli Stafford, Chunjiang Zhu	Improved Sourcewise Roundtrip Spanners with Constant Stretch.	COCOON (1)	2023	DBLP DOI BibTeX RDF
15	Fernanda Couto, Luís Felipe I. Cunha, Daniel Juventude, Leandro Santiago 0003	Strategies for generating tree spanners: Algorithms, heuristics and optimal graph classes.	Inf. Process. Lett.	2022	DBLP DOI BibTeX RDF
15	Mengshi Li, Jian Peng 0002, Shenggen Ju, Quanhui Liu, Hongyou Li, Weifa Liang, Jeffrey Xu Yu, Wenzheng Xu	Efficient algorithms for finding diversified top-k structural hole spanners in social networks.	Inf. Sci.	2022	DBLP DOI BibTeX RDF
15	Sujoy Bhore, Csaba D. Tóth	Euclidean Steiner Spanners: Light and Sparse.	SIAM J. Discret. Math.	2022	DBLP DOI BibTeX RDF
15	Adrian Dumitrescu, Anirban Ghosh 0002, Csaba D. Tóth	Sparse hop spanners for unit disk graphs.	Comput. Geom.	2022	DBLP DOI BibTeX RDF
15	Arnold Filtser, Ofer Neiman	Light Spanners for High Dimensional Norms via Stochastic Decompositions.	Algorithmica	2022	DBLP DOI BibTeX RDF
15	Stephen Alstrup, Søren Dahlgaard, Arnold Filtser, Morten Stöckel, Christian Wulff-Nilsen	Constructing light spanners deterministically in near-linear time.	Theor. Comput. Sci.	2022	DBLP DOI BibTeX RDF
15	Prafullkumar Tale	Sparsification lower bound for linear spanners in directed graphs.	Theor. Comput. Sci.	2022	DBLP DOI BibTeX RDF
15	Oliver Bendele, Dieter Rautenbach	Additive tree O(ρlog⁡n)-spanners from tree breadth ρ.	Theor. Comput. Sci.	2022	DBLP DOI BibTeX RDF
15	Prafullkumar Tale	Sparsification Lower Bound for Linear Spanners in Directed Graphs.	CoRR	2022	DBLP DOI BibTeX RDF
15	Arnold Filtser	Labeled Nearest Neighbor Search and Metric Spanners via Locality Sensitive Orderings.	CoRR	2022	DBLP DOI BibTeX RDF
15	Frederick Anderson, Anirban Ghosh 0002, Matthew Graham, Lucas Mougeot, David Wisnosky	Bounded-degree plane geometric spanners in practice.	CoRR	2022	DBLP DOI BibTeX RDF
15	Shimon Kogan, Merav Parter	Having Hope in Hops: New Spanners, Preservers and Lower Bounds for Hopsets.	CoRR	2022	DBLP DOI BibTeX RDF
15	Stav Ashur, Sariel Har-Peled	Local Spanners Revisited.	CoRR	2022	DBLP BibTeX RDF
15	Sujoy Bhore, Arnold Filtser, Hadi Khodabandeh, Csaba D. Tóth	Online Spanners in Metric Spaces.	CoRR	2022	DBLP BibTeX RDF
15	Merav Parter	Õptimal Vertex Fault-Tolerant Spanners in Õptimal Time: Sequential, Distributed and Parallel.	CoRR	2022	DBLP DOI BibTeX RDF
15	Marcel Bezdrighin, Michael Elkin, Mohsen Ghaffari 0001, Christoph Grunau, Bernhard Haeupler, Saeed Ilchi, Václav Rozhon	Deterministic Distributed Sparse and Ultra-Sparse Spanners and Connectivity Certificates.	CoRR	2022	DBLP DOI BibTeX RDF
15	Mohsen Ghaffari 0001, Christoph Grunau, Bernhard Haeupler, Saeed Ilchi, Václav Rozhon	Improved Distributed Network Decomposition, Hitting Sets, and Spanners, via Derandomization.	CoRR	2022	DBLP DOI BibTeX RDF
15	Sepehr Assadi, Michael Kapralov, Huacheng Yu	On Constructing Spanners from Random Gaussian Projections.	CoRR	2022	DBLP DOI BibTeX RDF
15	Sayan Bhattacharya, Thatchaphol Saranurak, Pattara Sukprasert	Simple Dynamic Spanners with Near-optimal Recourse against an Adaptive Adversary.	CoRR	2022	DBLP DOI BibTeX RDF
15	Diksha Goel, Hong Shen 0001, Hui Tian 0001, Mingyu Guo	Discovering Structural Hole Spanners in Dynamic Networks via Graph Neural Networks.	CoRR	2022	DBLP DOI BibTeX RDF
15	Fernanda Couto, Luís Felipe I. Cunha, Diego Ferraz	Simpler and efficient characterizations of tree t-spanners for graphs with few P4's and (k, l)-graphs.	CoRR	2022	DBLP DOI BibTeX RDF
15	Davide Bilò, Gianlorenzo D'Angelo, Luciano Gualà, Stefano Leucci 0001, Mirko Rossi	Sparse Temporal Spanners with Low Stretch.	CoRR	2022	DBLP DOI BibTeX RDF
15	Csaba D. Tóth	Minimum Weight Euclidean (1+ε)-Spanners.	CoRR	2022	DBLP DOI BibTeX RDF
15	Sujoy Bhore, Csaba D. Tóth	Euclidean Steiner Spanners: Light and Sparse.	CoRR	2022	DBLP DOI BibTeX RDF
15	Alan M. Frieze, Wesley Pegden	Spanners in randomly weighted graphs: Independent edge lengths.	Discret. Appl. Math.	2022	DBLP DOI BibTeX RDF
15	Damien Galant, Cédric Pilatte	A note on optimal degree-three spanners of the square lattice.	Discret. Math. Algorithms Appl.	2022	DBLP DOI BibTeX RDF
15	Kevin Buchin, Sariel Har-Peled, Dániel Oláh	Sometimes reliable spanners of almost linear size.	J. Comput. Geom.	2022	DBLP DOI BibTeX RDF
15	Sukanya Bhattacharjee, R. Inkulu	Vertex Fault-Tolerant Geometric Spanners for Weighted Points.	Int. J. Comput. Geom. Appl.	2022	DBLP DOI BibTeX RDF
15	Oswin Aichholzer, Manuel Borrazzo, Prosenjit Bose, Jean Cardinal, Fabrizio Frati, Pat Morin, Birgit Vogtenhuber	Drawing Graphs as Spanners.	Discret. Comput. Geom.	2022	DBLP DOI BibTeX RDF
15	Hung Le 0001, Cuong Than	Greedy Spanners in Euclidean Spaces Admit Sublinear Separators.	SODA	2022	DBLP DOI BibTeX RDF
15	Kevin Lu, Virginia Vassilevska Williams, Nicole Wein, Zixuan Xu	Better Lower Bounds for Shortcut Sets and Additive Spanners via an Improved Alternation Product.	SODA	2022	DBLP DOI BibTeX RDF
15	Hung Le 0001, Shay Solomon	Near-Optimal Spanners for General Graphs in (Nearly) Linear Time.	SODA	2022	DBLP DOI BibTeX RDF
15	Greg Bodwin, Michael Dinitz, Caleb Robelle	Partially Optimal Edge Fault-Tolerant Spanners.	SODA	2022	DBLP DOI BibTeX RDF
15	Renzo Gómez, Flávio Keidi Miyazawa, Yoshiko Wakabayashi	Minimum t-Spanners on Subcubic Graphs.	WALCOM	2022	DBLP DOI BibTeX RDF