Search results for "3-spanner"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
169	Feodor F. Dragan, Fedor V. Fomin, Petr A. Golovach	Spanners in Sparse Graphs.	ICALP (1)	2008	DBLP DOI BibTeX RDF
153	Anita Das 0001, B. S. Panda 0001, Rajendra P. Lal	A linear time algorithm for constructing tree 3-spanner in simple chordal bipartite graphs.	ICIT	2006	DBLP DOI BibTeX RDF
145	Arnab Bhattacharyya 0001, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff	Transitive-closure spanners.	SODA	2009	DBLP DOI BibTeX RDF
141	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
141	Michael Elkin, David Peleg	The Hardness of Approximating Spanner Problems.	Theory Comput. Syst.	2007	DBLP DOI BibTeX RDF
141	Michael Elkin, David Peleg	The Hardness of Approximating Spanner Problems.	STACS	2000	DBLP DOI BibTeX RDF
133	Shiri Chechik, Michael Langberg, David Peleg, Liam Roditty	Fault-tolerant spanners for general graphs.	STOC	2009	DBLP DOI BibTeX RDF	fault-tolerance, graphs, spanners
125	B. S. Panda 0001, Anita Das 0001	A Linear Time Algorithm for Constructing Tree 4-Spanner in 2-Trees.	CIT	2004	DBLP DOI BibTeX RDF	Tree Spanner, Distance in Graphs, 2-trees, Graph Algorithms
121	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
117	Michael Elkin, David Peleg	(1+epsilon, beta)-spanner constructions for general graphs.	STOC	2001	DBLP DOI BibTeX RDF
117	Michael Elkin, David Peleg	Strong Inapproximability of the Basic k-Spanner Problem.	ICALP	2000	DBLP DOI BibTeX RDF
109	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
109	Christian Schindelhauer, Klaus Volbert, Martin Ziegler 0001	Spanners, Weak Spanners, and Power Spanners for Wireless Networks.	ISAAC	2004	DBLP DOI BibTeX RDF
101	Khaled M. Alzoubi	Connected Dominating Set and its Induced Position-less Sparse Spanner For Mobile Ad Hoc Networks.	ISCC	2003	DBLP DOI BibTeX RDF	topological dilation, geometric dilation, connected dominating set, sparse spanner
97	Bilel Derbel, Cyril Gavoille, David Peleg, Laurent Viennot	Local Computation of Nearly Additive Spanners.	DISC	2009	DBLP DOI BibTeX RDF
97	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
89	Yu Wang 0003, Xiang-Yang Li 0001	Localized construction of bounded degree and planar spanner for wireless ad hoc networks.	DIALM-POMC	2003	DBLP DOI BibTeX RDF	wireless ad hoc networks, topology control, localized algorithm, spanner, planar, bounded degree
84	Andreas Wiese, Evangelos Kranakis	Local Construction and Coloring of Spanners of Location Aware Unit Disk Graphs.	WG	2008	DBLP DOI BibTeX RDF
84	Giorgio Ausiello, Paolo Giulio Franciosa, Giuseppe F. Italiano	Small Stretch Spanners on Dynamic Graphs.	ESA	2005	DBLP DOI BibTeX RDF
81	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
81	Sudhir Aggarwal, Daniel Barbará, Kalman Z. Meth	A Software Environment for the Specification and Analysis of Problems of Coordination and Concurrency.	IEEE Trans. Software Eng.	1988	DBLP DOI BibTeX RDF	SPANNER software environment, selection/resolution model, cluster variables, simulation, parallel programming, concurrency, distributed computing, specification, coordination, distributed processing, programming environments, concurrent programming, reachability analysis, software environment, dining philosophers, finite-state machine model
81	Yang Yang 0012, Yongding Zhu, Jinhui Xu 0001, Naoki Katoh	Geometric Spanner of Segments.	ISAAC	2007	DBLP DOI BibTeX RDF
81	Surender Baswana, Sandeep Sen	A Simple Linear Time Algorithm for Computing a (2k-1)-Spanner of O(n1+1/k) Size in Weighted Graphs.	ICALP	2003	DBLP DOI BibTeX RDF	Randomized algorithms, Shortest path, Graph algorithms
81	Michael Elkin, David Peleg	Approximating k-Spanner Problems for k>2.	IPCO	2001	DBLP DOI BibTeX RDF
81	Sunil Arya, Michiel H. M. Smid	Efficient Construction of a Bounded Degree Spanner with Low Weight.	ESA	1994	DBLP DOI BibTeX RDF
77	Yu Wang 0003, Xiang-Yang Li 0001	Minimum power assignment in wireless ad hoc networks with spanner property.	J. Comb. Optim.	2006	DBLP DOI BibTeX RDF	Graph theory, Wireless ad hoc networks, Spanner, Power assignment
72	Mohammad Ali Abam, Mark de Berg	Kinetic spanners in Rd.	SCG	2009	DBLP DOI BibTeX RDF	kinetic data structures, geometric spanners
72	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
72	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
72	Tamás Lukovszki	New Results of Fault Tolerant Geometric Spanners.	WADS	1999	DBLP DOI BibTeX RDF
72	Sándor P. Fekete, Jana Kremer	Tree Spanners in Planar Graphs.	WG	1998	DBLP DOI BibTeX RDF
65	Yu Wang 0003, Xiang-Yang Li 0001	Localized Construction of Bounded Degree and Planar Spanner for Wireless Ad Hoc Networks.	Mob. Networks Appl.	2006	DBLP DOI BibTeX RDF	Wireless ad hoc networks, topology control, localized algorithm, spanner, planar, bounded degree
60	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
60	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
60	Philippe Jacquet, Laurent Viennot	Remote-spanners: What to know beyond neighbors.	IPDPS	2009	DBLP DOI BibTeX RDF
60	Lee-Ad Gottlieb, Liam Roditty	Improved algorithms for fully dynamic geometric spanners and geometric routing.	SODA	2008	DBLP BibTeX RDF
60	Mohammad Ali Abam, Mark de Berg, Mohammad Farshi, Joachim Gudmundsson	Region-fault tolerant geometric spanners.	SODA	2007	DBLP BibTeX RDF
60	T.-H. Hubert Chan, Anupam Gupta 0001	Small hop-diameter sparse spanners for doubling metrics.	SODA	2006	DBLP DOI BibTeX RDF
60	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
60	Victor Chepoi, Feodor F. Dragan, Chenyu Yan	Additive Spanners for k-Chordal Graphs.	CIAC	2003	DBLP DOI BibTeX RDF
60	Dagmar Handke, Guy Kortsarz	Tree Spanners for Subgraphs and Related Tree Covering Problems.	WG	2000	DBLP DOI BibTeX RDF
60	Sudhir Aggarwal, Costas Courcoubetis, Pierre Wolper	Adding Liveness Properties to Coupled Finite-State Machines.	ACM Trans. Program. Lang. Syst.	1990	DBLP DOI BibTeX RDF
56	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
56	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
56	David Peleg, Liam Roditty	Localized Spanner Construction for Ad Hoc Networks with Variable Transmission Range.	ADHOC-NOW	2008	DBLP DOI BibTeX RDF
56	Lee-Ad Gottlieb, Liam Roditty	An Optimal Dynamic Spanner for Doubling Metric Spaces.	ESA	2008	DBLP DOI BibTeX RDF
56	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
56	Héctor Tejeda, Edgar Chávez, Juan A. Sánchez, Pedro M. Ruiz	Energy-Efficient Face Routing on the Virtual Spanner.	ADHOC-NOW	2006	DBLP DOI BibTeX RDF
56	Héctor Tejeda, Edgar Chávez, Juan A. Sánchez, Pedro M. Ruiz	A Virtual Spanner for Efficient Face Routing in Multihop Wireless Networks. (PDF / PS)	PWC	2006	DBLP DOI BibTeX RDF
56	Xiang-Yang Li 0001, Yu Wang 0003	Efficient Construction of Low Weight Bounded Degree Planar Spanner.	COCOON	2003	DBLP DOI BibTeX RDF
56	Jeffrey S. Salowe	On Euclidean Spanner Graphs with Small Degree.	SCG	1992	DBLP DOI BibTeX RDF
52	Yu Wang 0003, Xiang-Yang Li 0001	Distributed Spanner with Bounded Degree for Wireless Ad Hoc Networks.	IPDPS	2002	DBLP DOI BibTeX RDF	Wireless ad hoc networks, topology control, power consumption, spanner
48	Shantanu Das 0001, Beat Gfeller, Peter Widmayer	Computing Best Swaps in Optimal Tree Spanners.	ISAAC	2008	DBLP DOI BibTeX RDF
48	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
48	Iyad A. Kanj, Ljubomir Perkovic, Ge Xia	Computing Lightweight Spanners Locally.	DISC	2008	DBLP DOI BibTeX RDF
48	Joachim Gudmundsson, Michiel H. M. Smid	On Spanners of Geometric Graphs.	SWAT	2006	DBLP DOI BibTeX RDF
48	Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, Seth Pettie	New constructions of (alpha, beta)-spanners and purely additive spanners.	SODA	2005	DBLP BibTeX RDF
48	Béla Bollobás, Don Coppersmith, Michael Elkin	Sparse distance preservers and additive spanners.	SODA	2003	DBLP BibTeX RDF
48	Christian Laforest	Construction of Efficient Communication Sub-structures: Non-approximability Results and Polynomial sub-cases.	Euro-Par	2003	DBLP DOI BibTeX RDF
48	Paul D. Manuel, Bharati Rajan, Indra Rajasingh, Amutha Alaguvel	Tree Spanners, Cayley Graphs, and Diametrically Uniform Graphs.	WG	2003	DBLP DOI BibTeX RDF
44	Jehoshua Bruck, Jie Gao 0001, Anxiao Jiang	Localization and routing in sensor networks by local angle information.	ACM Trans. Sens. Networks	2009	DBLP DOI BibTeX RDF	planar spanner subgraph, Sensor networks, wireless networks, localization, embedding, geographical routing
44	Matthias Müller-Hannemann, Siamak Tazari	A Near Linear Time Approximation Scheme for Steiner Tree Among Obstacles in the Plane.	WADS	2007	DBLP DOI BibTeX RDF	Uniform Orientation Metric, Banyan, Planar Graph, Steiner Tree, Spanner, PTAS, Obstacles, Euclidean Metric
44	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
44	Jehoshua Bruck, Jie Gao 0001, Anxiao Jiang	Localization and routing in sensor networks by local angle information.	MobiHoc	2005	DBLP DOI BibTeX RDF	planar spanner subgraph, sensor networks, wireless networks, localization, embedding, geographical routing
44	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
44	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
44	Klaus Volbert	Experimental analysis of adjustable sectorized topologies for static ad hoc networks: extended abstract.	DIALM-POMC	2004	DBLP DOI BibTeX RDF	algorithms, ad hoc networks, topology control, spanner
44	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
44	Michelangelo Grigni	Approximate TSP in Graphs with Forbidden Minors.	ICALP	2000	DBLP DOI BibTeX RDF	TSP, separator, spanner, approximation scheme, graph minor, genus
44	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
44	Yongding Zhu, Jinhui Xu 0001, Yang Yang 0012, Naoki Katoh, Shin-ichi Tanigawa	Geometric Spanner of Objects under L1 Distance.	COCOON	2008	DBLP DOI BibTeX RDF
44	Shien-Ching Hwang, Gen-Huey Chen	The Minimum Spanner Problem on Butterfly Graphs.	ISPAN	2000	DBLP DOI BibTeX RDF
40	Nedal Ababneh, Anastasios Viglas, S. Selvakennedy, Nadia Boukhatem	A Topology Control Algorithm with Good Spanner Properties for Wireless Sensor Networks.	CNSR	2010	DBLP DOI BibTeX RDF	Wireless Sensor Networks, Connectivity, Topology Control, Spanner
40	Hongli Xu, Liusheng Huang, Gang Wang, Yindong Zhang	Spanner-Aware Relay Node Placement in Wireless Ad Hoc Sensor Networks.	MSN	2009	DBLP DOI BibTeX RDF	Wireless Sensor Networks, Approximation, Placement, Spanner
40	Philip N. Klein	A subset spanner for Planar graphs, : with application to subset TSP.	STOC	2006	DBLP DOI BibTeX RDF	traveling salesman problem, planar graph, spanner, approximation scheme
40	Keerti Choudhary, Omer Gold	Diameter Spanner, Eccentricity Spanner, and Approximating Extremal Graph Distances: Static, Dynamic, and Fault Tolerant.	CoRR	2018	DBLP BibTeX RDF
40	Goutham Ranganath, Vinod K. Kulathumani	FLOC-SPANNER: An O(1) Time, Locally Self-Stabilizing Algorithm for Geometric Spanner Construction in a Wireless Sensor Network.	Int. J. Distributed Sens. Networks	2014	DBLP DOI BibTeX RDF
37	Philipp Reindl-Spanner, Barbara Prommegger, Jochen Gensichen, Helmut Krcmar	Exploring the potentials of Patient-Generated Health Data for the treatment of depression.	ECIS	2023	DBLP BibTeX RDF
37	Philipp Reindl-Spanner, Barbara Prommegger, Jochen Gensichen, Helmut Krcmar	Insights on Patient-Generated Health Data in Healthcare: A Literature Review.	PACIS	2022	DBLP BibTeX RDF
37	M. Lytova, Michael Spanner, Isaac Tamblyn	Deep learning and high harmonic generation.	CoRR	2020	DBLP BibTeX RDF
37	Kyle Mills, Michael Spanner, Isaac Tamblyn	Deep learning and the Schrödinger equation.	CoRR	2017	DBLP BibTeX RDF
37	Manuel Burghardt, Sebastian Spanner, Thomas Schmidt 0011, Florian Fuchs, Katia Buchhop, Miriam Nickl, Christian Wolff 0001	Digitale Erschließung einer Sammlung von Volksliedern aus dem deutschsprachigen Raum.	DHd	2017	DBLP DOI BibTeX RDF
37	Manuel Burghardt, Sebastian Spanner	Allegro: User-centered Design of a Tool for the Crowdsourced Transcription of Handwritten Music Scores.	DATeCH	2017	DBLP DOI BibTeX RDF
37	Sebastian Spanner, Manuel Burghardt, Christian Wolff 0001	Twista - An Application for the Analysis and Visualization of Tailored Tweet Collections.	ISI	2015	DBLP DOI BibTeX RDF
37	Michael J. Assels, Dana Echtner, Michael Spanner, Serguei A. Mokhov, François Carrière, Manny Taveroff	Multifaceted Faculty Network Design and Management: Practice and Experience Report	CoRR	2011	DBLP BibTeX RDF
37	Michael J. Assels, Dana Echtner, Michael Spanner, Serguei A. Mokhov, François Carrière, Manny Taveroff	Multifaceted faculty network design and management: practice and experience.	C3S2E	2011	DBLP DOI BibTeX RDF
37	Nathan Charlton, Mick Gasson, Guido Gybels, Mike Spanner, Arnoud van Wijk	User Requirements for the Session Initiation Protocol (SIP) in Support of Deaf, Hard of Hearing and Speech-impaired Individuals.	RFC	2002	DBLP DOI BibTeX RDF
37	Pablo Rodriguez 0001, Christian Spanner, Ernst W. Biersack	Analysis of web caching architectures: hierarchical and distributed caching.	IEEE/ACM Trans. Netw.	2001	DBLP DOI BibTeX RDF	performance, World Wide Web (WWW), Caching, web
37	Christine A. Hlavka, Michael A. Spanner	Unmixing AVHRR imagery to assess clearcuts and forest regrowth in Oregon.	IEEE Trans. Geosci. Remote. Sens.	1995	DBLP DOI BibTeX RDF
37	Peng Gong, John R. Miller 0001, Michael A. Spanner	Forest canopy closure from classification and spectral unmixing of scene components-multisensor evaluation of an open canopy.	IEEE Trans. Geosci. Remote. Sens.	1994	DBLP DOI BibTeX RDF
37	A. King, A. Parker, M. Spanner, R. D. Wright	A speech display computer for use in schools for the deaf.	ICASSP	1982	DBLP DOI BibTeX RDF
36	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
36	Surender Baswana, Soumojit Sarkar	Fully dynamic algorithm for graph spanners with poly-logarithmic update time.	SODA	2008	DBLP BibTeX RDF
36	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
36	Prosenjit Bose, Michiel H. M. Smid, Daming Xu	Diamond Triangulations Contain Spanners of Bounded Degree.	ISAAC	2006	DBLP DOI BibTeX RDF
36	David P. Woodruff	Lower Bounds for Additive Spanners, Emulators, and More.	FOCS	2006	DBLP DOI BibTeX RDF
36	Surender Baswana	Dynamic Algorithms for Graph Spanners.	ESA	2006	DBLP DOI BibTeX RDF
36	Bilel Derbel, Cyril Gavoille	Fast Deterministic Distributed Algorithms for Sparse Spanners.	SIROCCO	2006	DBLP DOI BibTeX RDF
36	Jie Gao 0001, Leonidas J. Guibas, An Thanh Nguyen	Distributed Proximity Maintenance in Ad Hoc Mobile Networks.	DCOSS	2005	DBLP DOI BibTeX RDF
36	Kazuo Iwama, Andrzej Lingas, Masaki Okita	Max-stretch Reduction for Tree Spanners.	WADS	2005	DBLP DOI BibTeX RDF