Search results for "spanners"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
15	Anil Maheshwari, Michiel H. M. Smid, Norbert Zeh	I/O-efficient algorithms for computing planar geometric spanners.	Comput. Geom.	2008	DBLP DOI BibTeX RDF
15	Kazuo Iwama, Andrzej Lingas, Masaki Okita	Max-Stretch Reduction for Tree Spanners.	Algorithmica	2008	DBLP DOI BibTeX RDF	Tree spanner, Maximum stretch, Graph augmentation, Time complexity
15	Bilel Derbel, Cyril Gavoille	Fast deterministic distributed algorithms for sparse spanners.	Theor. Comput. Sci.	2008	DBLP DOI BibTeX RDF
15	Yefim Dinitz, Michael Elkin, Shay Solomon	Shallow, Low, and Light Trees, and Tight Lower Bounds for Euclidean Spanners	CoRR	2008	DBLP BibTeX RDF
15	Iyad A. Kanj, Ljubomir Perkovic	On Geometric Spanners of Euclidean and Unit Disk Graphs	CoRR	2008	DBLP BibTeX RDF
15	Mirela Damian, Sriram V. Pemmaraju	Localized Spanners for Wireless Networks	CoRR	2008	DBLP BibTeX RDF
15	Prosenjit Bose, Paz Carmi, Mathieu Couture	Spanners of Additively Weighted Point Sets	CoRR	2008	DBLP BibTeX RDF
15	Arnab Bhattacharyya 0001, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff	Transitive-Closure Spanners	CoRR	2008	DBLP BibTeX RDF
15	Shantanu Das 0001, Beat Gfeller, Peter Widmayer	Computing Best Swaps in Optimal Tree Spanners.	ISAAC	2008	DBLP DOI BibTeX RDF
15	Lee-Ad Gottlieb, Liam Roditty	Improved algorithms for fully dynamic geometric spanners and geometric routing.	SODA	2008	DBLP BibTeX RDF
15	Yefim Dinitz, Michael Elkin, Shay Solomon	Shallow-Low-Light Trees, and Tight Lower Bounds for Euclidean Spanners.	FOCS	2008	DBLP DOI BibTeX RDF
15	Feodor F. Dragan, Fedor V. Fomin, Petr A. Golovach	Spanners in Sparse Graphs.	ICALP (1)	2008	DBLP DOI BibTeX RDF
15	Feodor F. Dragan, Fedor V. Fomin, Petr A. Golovach	A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs.	MFCS	2008	DBLP DOI BibTeX RDF
15	Seth Pettie	Distributed algorithms for ultrasparse spanners and linear size skeletons.	PODC	2008	DBLP DOI BibTeX RDF
15	Iyad A. Kanj, Ljubomir Perkovic	On Geometric Spanners of Euclidean and Unit Disk Graphs.	STACS	2008	DBLP DOI BibTeX RDF
15	Prosenjit Bose, Paz Carmi, Mathieu Couture, Anil Maheshwari, Pat Morin, Michiel H. M. Smid	Spanners of Complete k -Partite Geometric Graphs.	LATIN	2008	DBLP DOI BibTeX RDF
15	Christian Schindelhauer, Klaus Volbert, Martin Ziegler 0001	Geometric spanners with applications in wireless networks.	Comput. Geom.	2007	DBLP DOI BibTeX RDF
15	Andreas Brandstädt, Feodor F. Dragan, Hoàng-Oanh Le, Van Bang Le, Ryuhei Uehara	Tree Spanners for Bipartite Graphs and Probe Interval Graphs.	Algorithmica	2007	DBLP DOI BibTeX RDF
15	Yon Dourisboure, Feodor F. Dragan, Cyril Gavoille, Chenyu Yan	Spanners for bounded tree-length graphs.	Theor. Comput. Sci.	2007	DBLP DOI BibTeX RDF
15	Prosenjit Bose, Paz Carmi, Mathieu Couture, Michiel H. M. Smid, Daming Xu	On a family of strong geometric spanners that admit local routing strategies	CoRR	2007	DBLP BibTeX RDF
15	Prosenjit Bose, Paz Carmi, Mathieu Couture, Anil Maheshwari, Pat Morin, Michiel H. M. Smid	Spanners of Complete $k$-Partite Geometric Graphs	CoRR	2007	DBLP BibTeX RDF
15	Prosenjit Bose, Paz Carmi, Mathieu Couture, Anil Maheshwari, Michiel H. M. Smid, Norbert Zeh	Geometric Spanners With Small Chromatic Number	CoRR	2007	DBLP BibTeX RDF
15	Gonzalo Navarro 0001, Rodrigo Paredes, Edgar Chávez	t-Spanners for metric space searching.	Data Knowl. Eng.	2007	DBLP DOI BibTeX RDF
15	Surender Baswana, Sandeep Sen	A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs.	Random Struct. Algorithms	2007	DBLP DOI BibTeX RDF
15	B. S. Panda 0001, Anita Das 0001	On tree 3-spanners in directed path graphs.	Networks	2007	DBLP DOI BibTeX RDF
15	Prosenjit Bose, Aaron Lee, Michiel H. M. Smid	On Generalized Diamond Spanners.	WADS	2007	DBLP DOI BibTeX RDF
15	Prosenjit Bose, Paz Carmi, Mathieu Couture, Anil Maheshwari, Michiel H. M. Smid, Norbert Zeh	Geometric Spanners with Small Chromatic Number.	WAOA	2007	DBLP DOI BibTeX RDF
15	Iyad A. Kanj, Ljubomir Perkovic, Ge Xia	Strictly-Localized Construction of Near-Optimal Power Spanners for Wireless Ad-Hoc Networks.	DIALM-POMC	2007	DBLP BibTeX RDF
15	Feodor F. Dragan, Chenyu Yan, Irina Lomonosov	Collective tree spanners of graphs.	SIAM J. Discret. Math.	2006	DBLP DOI BibTeX RDF
15	Feodor F. Dragan, Chenyu Yan, Derek G. Corneil	Collective Tree Spanners and Routing in AT-free Related Graphs.	J. Graph Algorithms Appl.	2006	DBLP DOI BibTeX RDF
15	Giorgio Ausiello, Paolo Giulio Franciosa, Giuseppe F. Italiano	Small Stretch Spanners on Dynamic Graphs.	J. Graph Algorithms Appl.	2006	DBLP DOI BibTeX RDF
15	Jie Gao 0001, Leonidas J. Guibas, An Thai Nguyen	Deformable spanners and applications.	Comput. Geom.	2006	DBLP DOI BibTeX RDF
15	Surender Baswana	Faster Streaming algorithms for graph spanners	CoRR	2006	DBLP BibTeX RDF
15	Michael Elkin	A near-optimal fully dynamic distributed algorithm for maintaining sparse spanners	CoRR	2006	DBLP BibTeX RDF
15	Martin Fürer, Shiva Prasad Kasiviswanathan	Spanners for Geometric Intersection Graphs	CoRR	2006	DBLP BibTeX RDF
15	Prosenjit Bose, Michiel H. M. Smid, Daming Xu	Diamond Triangulations Contain Spanners of Bounded Degree.	ISAAC	2006	DBLP DOI BibTeX RDF
15	Mikkel Thorup, Uri Zwick	Spanners and emulators with sublinear distance errors.	SODA	2006	DBLP DOI BibTeX RDF
15	Iyad A. Kanj, Ljubomir Perkovic	Improved Stretch Factor for Bounded-Degree Planar Power Spanners of Wireless Ad-Hoc Networks.	ALGOSENSORS	2006	DBLP DOI BibTeX RDF
15	Joachim Gudmundsson, Michiel H. M. Smid	On Spanners of Geometric Graphs.	SWAT	2006	DBLP DOI BibTeX RDF
15	Michiel H. M. Smid	Geometric spanners with few edges and degree five.	CATS	2006	DBLP BibTeX RDF
15	Edgar Chávez, Stefan Dobrev, Evangelos Kranakis, Jaroslav Opatrny, Ladislav Stacho, Jorge Urrutia	Local Construction of Planar Spanners in Unit Disk Graphs with Irregular Transmission Ranges.	LATIN	2006	DBLP DOI BibTeX RDF
15	Petra Berenbrink, Tom Friedetzky, Ján Manuch, Ladislav Stacho	(quasi) Spanners for Mobile Ad Hoc Networks.	J. Interconnect. Networks	2005	DBLP DOI BibTeX RDF
15	Béla Bollobás, Don Coppersmith, Michael Elkin	Sparse Distance Preservers and Additive Spanners.	SIAM J. Discret. Math.	2005	DBLP DOI BibTeX RDF
15	Tetsuo Asano, Mark de Berg, Otfried Cheong, Hazel Everett, Herman J. Haverkort, Naoki Katoh, Alexander Wolff 0001	Optimal spanners for axis-aligned rectangles.	Comput. Geom.	2005	DBLP DOI BibTeX RDF
15	Victor Chepoi, Feodor F. Dragan, Chenyu Yan	Additive sparse spanners for graphs with bounded length of largest induced cycle.	Theor. Comput. Sci.	2005	DBLP DOI BibTeX RDF
15	Jie Gao 0001, Leonidas J. Guibas, John Hershberger 0001, Li Zhang 0001, An Zhu	Geometric spanners for routing in mobile networks.	IEEE J. Sel. Areas Commun.	2005	DBLP DOI BibTeX RDF
15	Guillaume Fertin, Arthur L. Liestman, Thomas C. Shermer, Ladislav Stacho	Edge-disjoint spanners in Cartesian products of graphs.	Discret. Math.	2005	DBLP DOI BibTeX RDF
15	Daniel Russel, Leonidas J. Guibas	Exploring Protein Folding Trajectories Using Geometric Spanners.	Pacific Symposium on Biocomputing	2005	DBLP BibTeX RDF
15	Pankaj K. Agarwal, Yusu Wang 0001, Peng Yin	Lower bound for sparse Euclidean spanners.	SODA	2005	DBLP BibTeX RDF
15	Sergio Cabello, Bojan Mohar, Arjana Zitnik	Homotopic spanners.	EuroCG	2005	DBLP BibTeX RDF
15	Kazuo Iwama, Andrzej Lingas, Masaki Okita	Max-stretch Reduction for Tree Spanners.	WADS	2005	DBLP DOI BibTeX RDF
15	Joachim Gudmundsson, Giri Narasimhan, Michiel H. M. Smid	Fast Pruning of Geometric Spanners.	STACS	2005	DBLP DOI BibTeX RDF
15	Kishore Kothapalli, Christian Scheideler, Melih Onus, Andréa W. Richa	Constant density spanners for wireless ad-hoc networks.	SPAA	2005	DBLP DOI BibTeX RDF	ad hoc networks, self-stabilization, dominating set, spanner
15	Klaus Volbert	Geometric spanners for topology control in wireless networks		2005	RDF
15	Andreas Brandstädt, Feodor F. Dragan, Hoàng-Oanh Le, Van Bang Le	Tree spanners on chordal graphs: complexity and algorithms.	Theor. Comput. Sci.	2004	DBLP DOI BibTeX RDF
15	Arthur M. Farley, Andrzej Proskurowski, Daniel Zappala, Kurt J. Windisch	Spanners and message distribution in networks.	Discret. Appl. Math.	2004	DBLP DOI BibTeX RDF
15	Joachim Gudmundsson, Jan Vahrenhold	A Simple Algorithm for I/O-efficiently Pruning Dense Spanners.	Cache-Oblivious and Cache-Aware Algorithms	2004	DBLP BibTeX RDF
15	Joachim Gudmundsson, Jan Vahrenhold	I/O-Efficiently Pruning Dense Spanners.	JCDCG	2004	DBLP DOI BibTeX RDF
15	Jie Gao 0001, Leonidas J. Guibas, An Thanh Nguyen	Deformable spanners and applications.	SCG	2004	DBLP DOI BibTeX RDF	geometric k-center, proximity maintenance, spanner graphs, well-separated pair decomposition, collision detection, kinetic data structures, approximate nearest neighbor
15	Vincenzo Perrone, Akbar Zaheer, Bill McEvily	Free to Be Trusted? Organizational Constraints on Trust in Boundary Spanners.	Organ. Sci.	2003	DBLP DOI BibTeX RDF
15	Khaled M. Alzoubi, Xiang-Yang Li 0001, Yu Wang 0003, Peng-Jun Wan, Ophir Frieder	Geometric Spanners for Wireless Ad Hoc Networks.	IEEE Trans. Parallel Distributed Syst.	2003	DBLP DOI BibTeX RDF	wireless ad hoc networks, clustering, Delaunay triangulation, localized algorithm, Connected dominating set, spanner, unit disk graph
15	Khaled M. Alzoubi, Peng-Jun Wan, Ophir Frieder	Maximal Independent Set, Weakly-Connected Dominating Set, and Induced Spanners in Wireless Ad Hoc Networks.	Int. J. Found. Comput. Sci.	2003	DBLP DOI BibTeX RDF
15	Yu Wang 0003, Xiang-Yang Li 0001, Ophir Frieder	Distributed Spanners with Bounded Degree for Wireless Ad Hoc Networks.	Int. J. Found. Comput. Sci.	2003	DBLP DOI BibTeX RDF
15	Andreas Brandstädt, Feodor F. Dragan, Hoàng-Oanh Le, Van Bang Le, Ryuhei Uehara	Tree Spanners for Bipartite Graphs and Probe Interval Graphs.	WG	2003	DBLP DOI BibTeX RDF	Chordal bipartite graph, Interval bigraph, Probe interval graph, Tree spanner, NP-completeness
15	Paul D. Manuel, Bharati Rajan, Indra Rajasingh, Amutha Alaguvel	Tree Spanners, Cayley Graphs, and Diametrically Uniform Graphs.	WG	2003	DBLP DOI BibTeX RDF
15	Joachim Gudmundsson	Constructing Sparse t-Spanners with Small Separators.	FCT	2003	DBLP DOI BibTeX RDF
15	Khaled M. Alzoubi, Peng-Jun Wan, Ophir Frieder	Weakly-Connected Dominating Sets and Sparse Spanners in Wireless Ad Hoc Networks.	ICDCS	2003	DBLP DOI BibTeX RDF	weakly-connected dominating set, maximal independent set, sparse spanner
15	Gonzalo Navarro 0001, Rodrigo Paredes	Practical Constraction of Metric t-Spanners.	ALENEX	2003	DBLP BibTeX RDF
15	Joachim Gudmundsson, Christos Levcopoulos, Giri Narasimhan	Fast Greedy Algorithms for Constructing Sparse Geometric Spanners.	SIAM J. Comput.	2002	DBLP DOI BibTeX RDF
15	Andreas Brandstädt, Feodor F. Dragan, Hoàng-Oanh Le, Van Bang Le	Tree Spanners on Chordal Graphs: Complexity, Algorithms, Open Problems.	ISAAC	2002	DBLP DOI BibTeX RDF
15	Michelangelo Grigni, Papa A. Sissokho	Light spanners and approximate TSP in weighted graphs with forbidden minors.	SODA	2002	DBLP BibTeX RDF
15	Yu Wang 0003, Xiang-Yang Li 0001	Geometric Spanners for Wireless Ad Hoc Networks.	ICDCS	2002	DBLP DOI BibTeX RDF
15	Danny Z. Chen, Gautam Das 0001, Michiel H. M. Smid	Lower bounds for computing geometric spanners and approximate shortest paths.	Discret. Appl. Math.	2001	DBLP DOI BibTeX RDF
15	Sándor P. Fekete, Jana Kremer	Tree spanners in planar graphs.	Discret. Appl. Math.	2001	DBLP DOI BibTeX RDF
15	Dagmar Handke	Independent tree spanners: fault-tolerant spanning trees with constant distance guarantees.	Discret. Appl. Math.	2001	DBLP DOI BibTeX RDF
15	Christian Laforest, Arthur L. Liestman, Thomas C. Shermer, Dominique Sotteau	Edge-disjoint spanners of complete bipartite graphs.	Discret. Math.	2001	DBLP DOI BibTeX RDF
15	Shien-Ching Hwang, Gen-Huey Chen	Minimum spanners of butterfly graphs.	Networks	2001	DBLP DOI BibTeX RDF
15	William Duckworth, Michele Zito 0001	Sparse Hypercube 3-spanners.	Discret. Appl. Math.	2000	DBLP DOI BibTeX RDF
15	David Eppstein	Spanning Trees and Spanners.	Handbook of Computational Geometry	2000	DBLP DOI BibTeX RDF
15	José Cáceres, Clara I. Grima, Alberto Márquez 0001	Spanners in l1.	CCCG	2000	DBLP BibTeX RDF
15	Joachim Gudmundsson, Christos Levcopoulos, Giri Narasimhan	Improved Greedy Algorithms for Constructing Sparse Geometric Spanners.	SWAT	2000	DBLP DOI BibTeX RDF
15	Sunil Arya, David M. Mount, Michiel H. M. Smid	Dynamic algorithms for geometric spanners of small diameter: Randomized solutions.	Comput. Geom.	1999	DBLP DOI BibTeX RDF
15	Christian Laforest, Arthur L. Liestman, David Peleg, Thomas C. Shermer, Dominique Sotteau	Edge-disjoint spanners of complete graphs and complete digraphs.	Discret. Math.	1999	DBLP DOI BibTeX RDF
15	Hoàng-Oanh Le, Van Bang Le	Optimal tree 3-spanners in directed path graphs.	Networks	1999	DBLP DOI BibTeX RDF
15	Matthias Fischer 0001, Tamás Lukovszki, Martin Ziegler 0001	Partitioned neighborhood spanners of minimal outdegree.	CCCG	1999	DBLP BibTeX RDF
15	Tamás Lukovszki	New results on geometric spanners and their applications.		1999	RDF
15	David W. Krumme	An Optimal Disjoint Pair of Additive Spanners for the 3D Grid.	Parallel Process. Lett.	1998	DBLP DOI BibTeX RDF
15	Ulrik Brandes, Dagmar Handke	NP-Completeness Results for Minimum Planar Spanners.	Discret. Math. Theor. Comput. Sci.	1998	DBLP DOI BibTeX RDF
15	Guy Kortsarz, David Peleg	Generating Low-Degree 2-Spanners.	SIAM J. Comput.	1998	DBLP DOI BibTeX RDF
15	Edith Cohen	Fast Algorithms for Constructing t-Spanners and Paths with Stretch t.	SIAM J. Comput.	1998	DBLP DOI BibTeX RDF
15	Christos Levcopoulos, Giri Narasimhan, Michiel H. M. Smid	Efficient Algorithms for Constructing Fault-Tolerant Geometric Spanners.	STOC	1998	DBLP DOI BibTeX RDF
15	Satish Rao, Warren D. Smith	Approximating Geometrical Graphs via "Spanners" and "Banyans".	STOC	1998	DBLP DOI BibTeX RDF
15	Rabah Harbane, Carles Padró	Spanners of de Bruijn and Kautz Graphs.	Inf. Process. Lett.	1997	DBLP DOI BibTeX RDF
15	Rabah Harbane, Carles Padró	Spanners of Underlying Graphs of Iterated Line Digraphs.	Inf. Process. Lett.	1997	DBLP DOI BibTeX RDF
15	Gautam Das 0001, Giri Narasimhan	A Fast Algorithm for Constructing Sparse Euclidean Spanners.	Int. J. Comput. Geom. Appl.	1997	DBLP DOI BibTeX RDF
15	M. S. Madanlal, G. Venkatesan, C. Pandu Rangan	Tree 3-Spanners on Interval, Permutation and Regular Bipartite Graphs.	Inf. Process. Lett.	1996	DBLP DOI BibTeX RDF
15	Marie-Claude Heydemann, Joseph G. Peters, Dominique Sotteau	Spanners of Hypercube-Derived Networks.	SIAM J. Discret. Math.	1996	DBLP DOI BibTeX RDF
15	Arthur L. Liestman, Thomas C. Shermer, Christopher R. Stolte	Degree-constrained Spanners for Multidimensional Grids.	Discret. Appl. Math.	1996	DBLP DOI BibTeX RDF
15	Gautam Das 0001, Paul J. Heffernan	Constructing Degree-3 Spanners with Other Sparseness Properties.	Int. J. Found. Comput. Sci.	1996	DBLP DOI BibTeX RDF
15	S. Tsang, Milton H. Saier Jr.	A Simple Flexible Program for the Computational Analysis of Amyl Acyl Residue Distribution in Proteins: Application to the Distribution of Aromatic versus Aliphatic Hydrophobic Amino Acids in Transmembrane alpha-Helical Spanners of Integral Membrane Transport Proteins.	J. Comput. Biol.	1996	DBLP DOI BibTeX RDF