Search results for "spanners"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
212	Christian Schindelhauer, Klaus Volbert, Martin Ziegler 0001	Spanners, Weak Spanners, and Power Spanners for Wireless Networks.	ISAAC	2004	DBLP DOI BibTeX RDF
140	Feodor F. Dragan, Chenyu Yan	Collective Tree Spanners in Graphs with Bounded Genus, Chordality, Tree-Width, or Clique-Width.	ISAAC	2005	DBLP DOI BibTeX RDF
126	Philippe Jacquet, Laurent Viennot	Remote-spanners: What to know beyond neighbors.	IPDPS	2009	DBLP DOI BibTeX RDF
112	Arnab Bhattacharyya 0001, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff	Transitive-closure spanners.	SODA	2009	DBLP DOI BibTeX RDF
112	Feodor F. Dragan, Derek G. Corneil, Ekkehard Köhler, Yang Xiang	Additive Spanners for Circle Graphs and Polygonal Graphs.	WG	2008	DBLP DOI BibTeX RDF
112	Artur Czumaj, Hairong Zhao	Fault-tolerant geometric spanners.	SCG	2003	DBLP DOI BibTeX RDF	fault-tolerant spanners, computational geometry, greedy algorithms, spanners
105	Shiri Chechik, Michael Langberg, David Peleg, Liam Roditty	Fault-tolerant spanners for general graphs.	STOC	2009	DBLP DOI BibTeX RDF	fault-tolerance, graphs, spanners
100	Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, Seth Pettie	New constructions of (alpha, beta)-spanners and purely additive spanners.	SODA	2005	DBLP BibTeX RDF
98	Mohammad Ali Abam, Mark de Berg, Mohammad Farshi, Joachim Gudmundsson, Michiel H. M. Smid	Geometric Spanners for Weighted Point Sets.	ESA	2009	DBLP DOI BibTeX RDF
98	Seth Pettie	Low Distortion Spanners.	ICALP	2007	DBLP DOI BibTeX RDF
98	Feodor F. Dragan, Chenyu Yan, Irina Lomonosov	Collective Tree Spanners of Graphs.	SWAT	2004	DBLP DOI BibTeX RDF
98	Dagmar Handke	Independent Tree Spanners.	WG	1998	DBLP DOI BibTeX RDF
91	Giorgio Ausiello, Camil Demetrescu, Paolo Giulio Franciosa, Giuseppe F. Italiano, Andrea Ribichini	Graph Spanners in the Streaming Model: An Experimental Study.	Algorithmica	2009	DBLP DOI BibTeX RDF	Graph spanners, Data streams, Graph algorithms, Algorithm engineering, Experimental algorithmics
91	Mohammad Ali Abam, Mark de Berg, Mohammad Farshi, Joachim Gudmundsson	Region-Fault Tolerant Geometric Spanners.	Discret. Comput. Geom.	2009	DBLP DOI BibTeX RDF	Fault-tolerance, Geometric spanners, Geometric networks
85	Feodor F. Dragan, Chenyu Yan, Yang Xiang	Collective Additive Tree Spanners of Homogeneously Orderable Graphs.	LATIN	2008	DBLP DOI BibTeX RDF
85	T.-H. Hubert Chan, Michael Dinitz, Anupam Gupta 0001	Spanners with Slack.	ESA	2006	DBLP DOI BibTeX RDF
85	Feodor F. Dragan, Chenyu Yan, Derek G. Corneil	Collective Tree Spanners and Routing in AT-free Related Graphs.	WG	2004	DBLP DOI BibTeX RDF
85	Michael Elkin, Jian Zhang 0004	Efficient algorithms for constructing (1+, varepsilon;, beta)-spanners in the distributed and streaming models.	PODC	2004	DBLP DOI BibTeX RDF	almost shortest paths, streaming model, spanner
85	Barun Chandra, Gautam Das 0001, Giri Narasimhan, José Soares	New Sparseness Results on Graph Spanners.	SCG	1992	DBLP DOI BibTeX RDF
71	Mohammad Ali Abam, Mark de Berg, Mohammad Farshi, Joachim Gudmundsson	Region-fault tolerant geometric spanners.	SODA	2007	DBLP BibTeX RDF
71	Martin Fürer, Shiva Prasad Kasiviswanathan	Spanners for Geometric Intersection Graphs.	WADS	2007	DBLP DOI BibTeX RDF
71	Artur Czumaj, Hairong Zhao	Fault-Tolerant Geometric Spanners.	Discret. Comput. Geom.	2004	DBLP DOI BibTeX RDF
71	Mikkel Sigurd, Martin Zachariasen	Construction of Minimum-Weight Spanners.	ESA	2004	DBLP DOI BibTeX RDF
64	Liam Roditty, Mikkel Thorup, Uri Zwick	Roundtrip spanners and roundtrip routing in directed graphs.	ACM Trans. Algorithms	2008	DBLP DOI BibTeX RDF	roundtrip, Routing, shortest paths, distances, spanners
57	Iyad A. Kanj, Ge Xia, Fenghui Zhang	Local Construction of Spanners in the 3-D Space.	DCOSS	2009	DBLP DOI BibTeX RDF
57	Andreas Wiese, Evangelos Kranakis	Local Construction and Coloring of Spanners of Location Aware Unit Disk Graphs.	WG	2008	DBLP DOI BibTeX RDF
57	Michael Elkin	Streaming and Fully Dynamic Centralized Algorithms for Constructing and Maintaining Sparse Spanners.	ICALP	2007	DBLP DOI BibTeX RDF
57	Surender Baswana	Dynamic Algorithms for Graph Spanners.	ESA	2006	DBLP DOI BibTeX RDF
57	Bilel Derbel, Cyril Gavoille	Fast Deterministic Distributed Algorithms for Sparse Spanners.	SIROCCO	2006	DBLP DOI BibTeX RDF
57	Mohammad Farshi, Joachim Gudmundsson	Experimental Study of Geometric t-Spanners.	ESA	2005	DBLP DOI BibTeX RDF
57	Liam Roditty, Mikkel Thorup, Uri Zwick	Deterministic Constructions of Approximate Distance Oracles and Spanners.	ICALP	2005	DBLP DOI BibTeX RDF
57	Yon Dourisboure, Cyril Gavoille	Sparse Additive Spanners for Bounded Tree-Length Graphs.	SIROCCO	2004	DBLP DOI BibTeX RDF
57	Béla Bollobás, Don Coppersmith, Michael Elkin	Sparse distance preservers and additive spanners.	SODA	2003	DBLP BibTeX RDF
57	Victor Chepoi, Feodor F. Dragan, Chenyu Yan	Additive Spanners for k-Chordal Graphs.	CIAC	2003	DBLP DOI BibTeX RDF
50	T.-H. Hubert Chan, Anupam Gupta 0001	Small Hop-diameter Sparse Spanners for Doubling Metrics.	Discret. Comput. Geom.	2009	DBLP DOI BibTeX RDF	Hop diameter, Algorithms, Doubling metrics, Sparse spanners
50	Mirela Damian, Nagesh Javali	Distributed construction of bounded-degree low-interference spanners of low weight.	MobiHoc	2008	DBLP DOI BibTeX RDF	quasi unit disk graphs, wireless ad-hoc networks, interference, topology control, spanners
50	Bilel Derbel, Cyril Gavoille, David Peleg	Deterministic Distributed Construction of Linear Stretch Spanners in Polylogarithmic Time.	DISC	2007	DBLP DOI BibTeX RDF	graph spanners, distributed algorithms, time complexity
50	Michael Elkin	A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners.	PODC	2007	DBLP DOI BibTeX RDF	distributed dynamic algorithms, spanners
50	Prosenjit Bose, Joachim Gudmundsson, Michiel H. M. Smid	Constructing Plane Spanners of Bounded Degree and Low Weight.	Algorithmica	2005	DBLP DOI BibTeX RDF	Low weight graphs, Computational geometry, Planar graphs, Spanners, Bounded degree graphs
50	Christos Levcopoulos, Giri Narasimhan, Michiel H. M. Smid	Improved Algorithms for Constructing Fault-Tolerant Spanners.	Algorithmica	2002	DBLP DOI BibTeX RDF	Well-separated pairs, Fault-tolerance, Computational geometry, Spanners
48	Michael Elkin	Computing almost shortest paths.	ACM Trans. Algorithms	2005	DBLP DOI BibTeX RDF	almost shortest paths, Graph algorithms, spanners
43	Sanjiv Kapoor, Xiang-Yang Li 0001	Geodesic Spanners on Polyhedral Surfaces.	ISAAC	2009	DBLP DOI BibTeX RDF
43	Iyad A. Kanj, Ljubomir Perkovic, Ge Xia	Computing Lightweight Spanners Locally.	DISC	2008	DBLP DOI BibTeX RDF
43	Mohammad Farshi, Joachim Gudmundsson	Experimental Study of Geometric t-Spanners: A Running Time Comparison.	WEA	2007	DBLP DOI BibTeX RDF
43	Giorgio Ausiello, Camil Demetrescu, Paolo Giulio Franciosa, Giuseppe F. Italiano, Andrea Ribichini	Small Stretch Spanners in the Streaming Model: New Algorithms and Experiments.	ESA	2007	DBLP DOI BibTeX RDF
43	Prosenjit Bose, Paz Carmi, Mathieu Couture, Michiel H. M. Smid, Daming Xu	On a Family of Strong Geometric Spanners That Admit Local Routing Strategies.	WADS	2007	DBLP DOI BibTeX RDF
43	David P. Woodruff	Lower Bounds for Additive Spanners, Emulators, and More.	FOCS	2006	DBLP DOI BibTeX RDF
43	Liam Roditty, Mikkel Thorup, Uri Zwick	Roundtrip spanners and roundtrip routing in directed graphs.	SODA	2002	DBLP BibTeX RDF
43	Gonzalo Navarro 0001, Rodrigo Paredes, Edgar Chávez	t-Spanners as a Data Structure for Metric Space Searching.	SPIRE	2002	DBLP DOI BibTeX RDF
43	Tamás Lukovszki	New Results of Fault Tolerant Geometric Spanners.	WADS	1999	DBLP DOI BibTeX RDF
43	Ulrik Brandes, Dagmar Handke	NP-Completness Results for Minimum Planar Spanners.	WG	1997	DBLP DOI BibTeX RDF
43	Gautam Das 0001, Giri Narasimhan	A Fast Algorithm for Constructing Sparse Euclidean Spanners.	SCG	1994	DBLP DOI BibTeX RDF
43	Shuichi Ueno, Michihiro Yamazaki	Graph Spanners and Connectivity.	ISAAC	1992	DBLP DOI BibTeX RDF
42	Mohammad Ali Abam, Paz Carmi, Mohammad Farshi, Michiel H. M. Smid	On the Power of the Semi-Separated Pair Decomposition.	WADS	2009	DBLP DOI BibTeX RDF
42	David Peleg, Liam Roditty	Localized Spanner Construction for Ad Hoc Networks with Variable Transmission Range.	ADHOC-NOW	2008	DBLP DOI BibTeX RDF
42	Natalia Levina, Emmanuelle Vaast	Turning Collaboration into Transaction: A Case of Intranet Use in Boundary-Spanning Practices.	HICSS	2005	DBLP DOI BibTeX RDF
42	Shien-Ching Hwang, Gen-Huey Chen	The Minimum Spanner Problem on Butterfly Graphs.	ISPAN	2000	DBLP DOI BibTeX RDF
36	Mohammad Ali Abam, Mark de Berg	Kinetic spanners in Rd.	SCG	2009	DBLP DOI BibTeX RDF	kinetic data structures, geometric spanners
36	Joachim Gudmundsson, Christos Levcopoulos, Giri Narasimhan, Michiel H. M. Smid	Approximate distance oracles for geometric spanners.	ACM Trans. Algorithms	2008	DBLP DOI BibTeX RDF	approximation algorithm, computational geometry, Shortest paths, spanners, geometric graphs
36	Liam Roditty	Fully dynamic geometric spanners.	SCG	2007	DBLP DOI BibTeX RDF	algorithms, dynamic, geometry, spanners
36	Sunil Arya, David M. Mount, Michiel H. M. Smid	Randomized and deterministic algorithms for geometric spanners of small diameter	FOCS	1994	DBLP DOI BibTeX RDF	randomized algorithms, directed graph, deterministic algorithms, insertions, deletions, geometric spanners
36	Edith Cohen	Fast algorithms for constructing t-spanners and paths with stretch t	FOCS	1993	DBLP DOI BibTeX RDF	pairwise-covers, t-spanners constructions, paths with stretch, minimum-weight path, weighted undirected graph, exact shortest paths algorithms, randomized algorithm, deterministic algorithm, vertices, weighted graph
34	Mikkel Thorup, Uri Zwick	Approximate distance oracles.	J. ACM	2005	DBLP DOI BibTeX RDF	Approximate distance oracles, distance queries, shortest paths, distances, spanners, distance labelings
34	Reuven Bar-Yehuda, Dror Rawitz	Efficient Algorithms for Integer Programs with Two Variables per Constraint.	Algorithmica	2001	DBLP DOI BibTeX RDF	Well-separated pairs, Fault-tolerance, Computational geometry, Spanners
31	Glencora Borradaile, Hung Le 0001	Light spanners for bounded treewidth graphs imply light spanners for $H$-minor-free graphs.	CoRR	2017	DBLP BibTeX RDF
31	Shiri Chechik, Quentin Godfroy, David Peleg	Multipath Spanners via Fault-Tolerant Spanners.	MedAlg	2012	DBLP DOI BibTeX RDF
31	Quentin Godfroy	From spanners to multipath spanners. (Des spanneurs aux spanneurs multichemins).		2012	RDF
31	Cyril Gavoille, Quentin Godfroy, Laurent Viennot	Node-Disjoint Multipath Spanners and their Relationship with Fault-Tolerant Spanners	CoRR	2011	DBLP BibTeX RDF
31	Cyril Gavoille, Quentin Godfroy, Laurent Viennot	Node-Disjoint Multipath Spanners and Their Relationship with Fault-Tolerant Spanners.	OPODIS	2011	DBLP DOI BibTeX RDF
31	Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, Seth Pettie	Additive spanners and (alpha, beta)-spanners.	ACM Trans. Algorithms	2010	DBLP DOI BibTeX RDF
31	Iyad A. Kanj, Ljubomir Perkovic, Ge Xia	On Spanners and Lightweight Spanners of Geometric Graphs.	SIAM J. Comput.	2010	DBLP DOI BibTeX RDF
29	Mirela Damian, Nagesh Javali	Distributed construction of low-interference spanners.	Distributed Comput.	2009	DBLP DOI BibTeX RDF	Topology, Wireless ad hoc network, Interference, Spanner, Unit disk graph
29	Iyad A. Kanj	On Spanners of Geometric Graphs.	TAMC	2009	DBLP DOI BibTeX RDF
29	Surender Baswana, Soumojit Sarkar	Fully dynamic algorithm for graph spanners with poly-logarithmic update time.	SODA	2008	DBLP BibTeX RDF
29	Prosenjit Bose, Paz Carmi, Mathieu Couture	Spanners of Additively Weighted Point Sets.	SWAT	2008	DBLP DOI BibTeX RDF
29	Michael Elkin, Jian Zhang 0004	Efficient algorithms for constructing (1+epsilon, beta)-spanners in the distributed and streaming models.	Distributed Comput.	2006	DBLP DOI BibTeX RDF	Almost shortest paths, Streaming model, Spanner
29	T.-H. Hubert Chan, Anupam Gupta 0001	Small hop-diameter sparse spanners for doubling metrics.	SODA	2006	DBLP DOI BibTeX RDF
29	Feodor F. Dragan, Chenyu Yan	Network Flow Spanners.	LATIN	2006	DBLP DOI BibTeX RDF
29	Giorgio Ausiello, Paolo Giulio Franciosa, Giuseppe F. Italiano	Small Stretch Spanners on Dynamic Graphs.	ESA	2005	DBLP DOI BibTeX RDF
29	Derek G. Corneil, Feodor F. Dragan, Ekkehard Köhler, Chenyu Yan	Collective Tree 1-Spanners for Interval Graphs.	WG	2005	DBLP DOI BibTeX RDF
29	Prosenjit Bose, Joachim Gudmundsson, Michiel H. M. Smid	Constructing Plane Spanners of Bounded Degree and Low Weight.	ESA	2002	DBLP DOI BibTeX RDF
29	Guy Kortsarz	On the Hardness of Approximating Spanners.	Algorithmica	2001	DBLP DOI BibTeX RDF
29	Menelaos I. Karavelas, Leonidas J. Guibas	Static and kinetic geometric spanners with applications.	SODA	2001	DBLP BibTeX RDF
29	Anil Maheshwari, Michiel H. M. Smid, Norbert Zeh	I/O-Efficient Shortest Path Queries in Geometric Spanners.	WADS	2001	DBLP DOI BibTeX RDF
29	Dagmar Handke, Guy Kortsarz	Tree Spanners for Subgraphs and Related Tree Covering Problems.	WG	2000	DBLP DOI BibTeX RDF
29	Matthias Fischer 0001, Tamás Lukovszki, Martin Ziegler 0001	Geometric Searching in Walkthrough Animations with Weak Spanners in Real Time.	ESA	1998	DBLP DOI BibTeX RDF
29	Sándor P. Fekete, Jana Kremer	Tree Spanners in Planar Graphs.	WG	1998	DBLP DOI BibTeX RDF
29	Guy Kortsarz	On the Hardness of Approximation Spanners.	APPROX	1998	DBLP DOI BibTeX RDF
29	Christian Laforest, Arthur L. Liestman, Thomas C. Shermer, Dominique Sotteau	Edge Disjoint Graph Spanners of Complete Graphs and Complete Digraphs.	HICSS (1)	1997	DBLP DOI BibTeX RDF
29	Weifa Liang, Richard P. Brent	Constructing the Spanners of Graphs in Parallel.	IPPS	1996	DBLP DOI BibTeX RDF
29	Ingo Althöfer, Gautam Das 0001, David P. Dobkin, Deborah Joseph	Generating Sparse Spanners for Weighted Graphs.	SWAT	1990	DBLP DOI BibTeX RDF
28	Prosenjit Bose, Paz Carmi, Mohammad Farshi, Anil Maheshwari, Michiel H. M. Smid	Computing the Greedy Spanner in Near-Quadratic Time.	SWAT	2008	DBLP DOI BibTeX RDF
28	Jörg Derungs, Riko Jacob, Peter Widmayer	Approximate Shortest Paths Guided by a Small Index.	WADS	2007	DBLP DOI BibTeX RDF
28	Hubert Tsz-Hong Chan, Anupam Gupta 0001, Bruce M. Maggs, Shuheng Zhou	On hierarchical routing in doubling metrics.	SODA	2005	DBLP BibTeX RDF
28	Michael Elkin	Computing almost shortest paths.	PODC	2001	DBLP DOI BibTeX RDF
20	Mohammad Ali Abam, Sariel Har-Peled	New constructions of SSPDs and their applications.	SCG	2010	DBLP DOI BibTeX RDF	separated pair decomposition, separators, geometric spanners
20	Pascal von Rickenbach, Roger Wattenhofer, Aaron Zollinger	Algorithmic models of interference in wireless ad hoc and sensor networks.	IEEE/ACM Trans. Netw.	2009	DBLP DOI BibTeX RDF	network spanners, modeling, interference, topology control, network connectivity, algorithmic analysis
20	Mohammad Ali Abam, Mark de Berg, Joachim Gudmundsson	A simple and efficient kinetic spanner.	SCG	2008	DBLP DOI BibTeX RDF	kinetic data structures, geometric spanners
20	Surender Baswana, Sandeep Sen	Approximate distance oracles for unweighted graphs in expected O(n2) time.	ACM Trans. Algorithms	2006	DBLP DOI BibTeX RDF	Approximate distance oracles, distance queries, shortest paths, distances, spanners
20	Mirela Damian, Saurav Pandit, Sriram V. Pemmaraju	Local approximation schemes for topology control.	PODC	2006	DBLP DOI BibTeX RDF	wireless ad-hoc networks, topology control, spanners, unit ball graphs