Search results for "O(log n) time"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
2	Stephan Olariu, James L. Schwing, Jingyuan Zhang	Optimal Parallel Algorithms for Problems Modeled by a Family of Intervals.	IEEE Trans. Parallel Distrib. Syst.	1992	DBLP DOI BibTeX RDF	family of intervals, cost-optimal parallel algorithms, O(log n) time, scheduling, parallel algorithms, parallel algorithms, computational complexity, EREW-PRAM model, computational tools
1	Leonid Barenboim, Michael Elkin	Deterministic distributed vertex coloring in polylogarithmic time.	PODC	2010	DBLP DOI BibTeX RDF	arbdefective-coloring, arboricity, partial-orientation
1	Jen-Yeu Chen, Gopal Pandurangan	Optimal gossip-based aggregate computation.	SPAA	2010	DBLP DOI BibTeX RDF	distributed randomized protocols, lower bounds, probabilistic analysis, gossip-based protocols, aggregate computation
1	Zvika Brakerski, Boaz Patt-Shamir	Distributed discovery of large near-cliques.	PODC	2009	DBLP DOI BibTeX RDF	randomized algorithms, communication networks, property testing, clique
1	Johannes Schneider, Roger Wattenhofer	Coloring unstructured wireless multi-hop networks.	PODC	2009	DBLP DOI BibTeX RDF	bounded independence graphs, growth bounded graphs, unstructured radio networks, sensor networks, parallel algorithms, ad hoc networks, distributed algorithms, coloring, local algorithms, unit disk graphs
1	Bogdan S. Chlebus, Dariusz R. Kowalski	Locally scalable randomized consensus for synchronous crash failures.	SPAA	2009	DBLP DOI BibTeX RDF	bit communication complexity, graph expansion, fault tolerance, scalability, lower bound, message passing, randomization, consensus, synchrony
1	Rolf Hoffmann	The GCA-w Massively Parallel Model.	PaCT	2009	DBLP DOI BibTeX RDF	Massively Parallel Model, Global Cellular Automata, GCA with Write Access, Dynamic Neighborhood, Dynamic Cell Activation, GCA-w Applications, GCA-w Architecture
1	Mohammad Ali Abam, Mark de Berg, Sheung-Hung Poon, Bettina Speckmann	Kinetic Collision Detection for Convex Fat Objects.	Algorithmica	2009	DBLP DOI BibTeX RDF	Collision detection, Kinetic data structures, Fat objects
1	Amotz Bar-Noy, Mordecai J. Golin, Yan Zhang	Online Dynamic Programming Speedups.	Theory Comput. Syst.	2009	DBLP DOI BibTeX RDF	Dynamic programming, Monge property
1	Timothy M. Chan	Dynamic coresets.	Symposium on Computational Geometry	2008	DBLP DOI BibTeX RDF	approximation algorithms, randomization, dynamic data structures, geometric optimization, word ram
1	Daniel Berend, Michael Segal, Hanan Shpungin	Power efficient resilience and lifetime in wireless ad-hoc networks.	FOWANC	2008	DBLP DOI BibTeX RDF	strong connectivity, fault tolerance, wireless ad-hoc networks, topology control, energy consumption, network lifetime
1	Guy E. Blelloch	Space-efficient dynamic orthogonal point location, segment intersection, and range reporting.	SODA	2008	DBLP DOI BibTeX RDF
1	Robert Elsässer, Thomas Sauerwald	The power of memory in randomized broadcasting.	SODA	2008	DBLP DOI BibTeX RDF
1	Zvi Lotker, Boaz Patt-Shamir, Seth Pettie	Improved distributed approximate matching.	SPAA	2008	DBLP DOI BibTeX RDF	matching
1	Daniel A. Spielman, Nikhil Srivastava	Graph sparsification by effective resistances.	STOC	2008	DBLP DOI BibTeX RDF	electrical flows, random sampling, spectral graph theory
1	Mostafa Vahedi, A. Frank van der Stappen	Caging convex polygons with three fingers.	IROS	2008	DBLP DOI BibTeX RDF
1	Xuerong Feng, Chunlei Liu, Jun Kong	Sorting on Partially Connected Mesh Networks.	ITNG	2008	DBLP DOI BibTeX RDF	Parallel processing, Mesh network, Sorting network, Sorting algorithm
1	Yevgeny Schreiber, Micha Sharir	An Optimal-Time Algorithm for Shortest Paths on a Convex Polytope in Three Dimensions.	Discrete & Computational Geometry	2008	DBLP DOI BibTeX RDF	Continuous Dijkstra, Polytope surface, Shortest path, Unfolding, Geodesics, Wavefront, Shortest path map
1	Siu-Wing Cheng, Hyeon-Suk Na, Antoine Vigneron, Yajun Wang	Querying approximate shortest paths in anisotropic regions.	Symposium on Computational Geometry	2007	DBLP DOI BibTeX RDF	data structures, computational geometry, shortest path
1	Yevgeny Schreiber	Shortest paths on realistic polyhedra.	Symposium on Computational Geometry	2007	DBLP DOI BibTeX RDF	continuous Dijkstra, realistic, shortest path, terrain, wavefront, polyhedral surface, shortest path map
1	Sergio Cabello, Erin W. Chambers	Multiple source shortest paths in a genus g graph.	SODA	2007	DBLP DOI BibTeX RDF
1	Yijie Han	Optimal parallel selection.	ACM Transactions on Algorithms	2007	DBLP DOI BibTeX RDF	Parallel algorithms, selection, EREW PRAM
1	Andrew N. Edmonds	Using concept structures for efficient document comparison and location.	CIDM	2007	DBLP DOI BibTeX RDF
1	Hazem M. Bahig, Hatem M. Bahig	Optimal Parallel Merging by Counting.	ITNG	2007	DBLP DOI BibTeX RDF
1	Yamin Li, Shietung Peng, Wanming Chu	Efficient Algorithms for Finding a Trunk on a Tree Network and Its Applications.	PDCAT	2007	DBLP DOI BibTeX RDF
1	Joong Chae Na, Raffaele Giancarlo, Kunsoo Park	On-Line Construction of Two-Dimensional Suffix Trees in O(n2 log n) Time.	Algorithmica	2007	DBLP DOI BibTeX RDF
1	Mikkel Thorup	Fully-Dynamic Min-Cut.	Combinatorica	2007	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000): 68Q25, 68W05, 94C12, 94C15, 90B25, 68R10, 05C85, 05C40, 90B10
1	Timothy M. Chan	Point Location in o(log n) Time, Voronoi Diagrams in o(n log n) Time, and Other Transdichotomous Results in Computational Geometry.	FOCS	2006	DBLP DOI BibTeX RDF
1	Yevgeny Schreiber, Micha Sharir	An optimal-time algorithm for shortest paths on a convex polytope in three dimensions.	Symposium on Computational Geometry	2006	DBLP DOI BibTeX RDF	continuous Dijkstra, polytope surface, shortest path, unfolding, geodesics, wavefront, shortest path map
1	Sriram V. Pemmaraju, Imran A. Pirwani	Energy conservation via domatic partitions.	MobiHoc	2006	DBLP DOI BibTeX RDF	domatic partition, growth-bounded graphs, distributed algorithms, metric space, dominating sets, unit disk graphs, maximal independent sets, network decomposition, doubling dimension, unit ball graphs
1	Richard Cole, Lee-Ad Gottlieb	Searching dynamic point sets in spaces with bounded doubling dimension.	STOC	2006	DBLP DOI BibTeX RDF	approximate nearest neighbor search
1	Lilian Buzer	Digital Line Recognition, Convex Hull, Thickness, a Unified and Logarithmic Technique.	IWCIA	2006	DBLP DOI BibTeX RDF	digital line, logarithmic complexity, DSS, dynamic, recognition, convex hull, online, incremental, union
1	Boris Aronov, Prosenjit Bose, Erik D. Demaine, Joachim Gudmundsson, John Iacono, Stefan Langerman, Michiel H. M. Smid	Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams.	LATIN	2006	DBLP DOI BibTeX RDF
1	Veli Mäkinen, Gonzalo Navarro	Position-Restricted Substring Searching.	LATIN	2006	DBLP DOI BibTeX RDF
1	Iwona Bialynicka-Birula, Roberto Grossi	Amortized Rigidness in Dynamic Cartesian Trees.	STACS	2006	DBLP DOI BibTeX RDF
1	Chung Keung Poon, Wai Keung Yiu	Opportunistic data structures for range queries.	J. Comb. Optim.	2006	DBLP DOI BibTeX RDF
1	Gianni Franceschini, Roberto Grossi	Optimal Implicit Dictionaries over Unbounded Universes.	Theory Comput. Syst.	2006	DBLP DOI BibTeX RDF
1	David Y. Zhang, Bernard Yurke	A DNA Superstructure-based Replicator without Product Inhibition.	Natural Computing	2006	DBLP DOI BibTeX RDF	DNA based polymers, DNA motors, self-replication
1	Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer	On the locality of bounded growth.	PODC	2005	DBLP DOI BibTeX RDF	bounded growth, distributed algorithms, locality, dominating sets, packing, covering, unit disk graphs, maximal independent set, network decomposition, doubling dimension
1	Pankaj K. Agarwal, Lars Arge, Ke Yi	An optimal dynamic interval stabbing-max data structure?	SODA	2005	DBLP DOI BibTeX RDF
1	Philip N. Klein	Multiple-source shortest paths in planar graphs.	SODA	2005	DBLP DOI BibTeX RDF
1	Rina Panigrahy	Efficient hashing with lookups in two memory accesses.	SODA	2005	DBLP DOI BibTeX RDF
1	Stephen Alstrup, Jacob Holm, Kristian de Lichtenberg, Mikkel Thorup	Maintaining information in fully dynamic trees with top trees.	ACM Transactions on Algorithms	2005	DBLP DOI BibTeX RDF	Fully dynamic forest
1	Pi-Chung Wang, Yuan-Rung Yang, Chun-Liang Lee, Hung-Yi Chang	A Memory-Efficient Huffman Decoding Algorithm.	AINA	2005	DBLP DOI BibTeX RDF
1	Takashi Yamanoue	Sharing the Same Operation with a Large Number of Users Using P2P.	ICITA	2005	DBLP DOI BibTeX RDF
1	Alexander Kesselman, Dariusz R. Kowalski	Fast Distributed Algorithm for Convergecast in Ad Hoc Geometric Radio Networks.	WONS	2005	DBLP DOI BibTeX RDF
1	Yingwu Zhu, Yiming Hu	Efficient, Proximity-Aware Load Balancing for DHT-Based P2P Systems.	IEEE Trans. Parallel Distrib. Syst.	2005	DBLP DOI BibTeX RDF	Proximity-aware, virtual server, peer-to-peer, load balancing
1	Joong Chae Na, Raffaele Giancarlo, Kunsoo Park	O(n2log n) Time On-Line Construction of Two-Dimensional Suffix Trees.	COCOON	2005	DBLP DOI BibTeX RDF
1	Chung Keung Poon, Wai Keung Yiu	Opportunistic Data Structures for Range Queries.	COCOON	2005	DBLP DOI BibTeX RDF
1	Yan Wang, Deqiang Wang, Wei Liu, Baoyu Tian	Efficient Parallel Algorithms for Constructing a k-Tree Center and a k-Tree Core of a Tree Network.	ISAAC	2005	DBLP DOI BibTeX RDF
1	Amihood Amir, Tsvi Kopelowitz, Moshe Lewenstein, Noa Lewenstein	Towards Real-Time Suffix Tree Construction.	SPIRE	2005	DBLP DOI BibTeX RDF
1	Fabian Kuhn, Thomas Moscibroda, Tim Nieberg, Roger Wattenhofer	Fast Deterministic Distributed Maximal Independent Set Computation on Growth-Bounded Graphs.	DISC	2005	DBLP DOI BibTeX RDF
1	Pankaj K. Agarwal, Yusu Wang, Hai Yu	A 2D kinetic triangulation with near-quadratic topological changes.	Symposium on Computational Geometry	2004	DBLP DOI BibTeX RDF	triangulation, random sampling, kinetic data structures
1	Mayur Datar, Nicole Immorlica, Piotr Indyk, Vahab S. Mirrokni	Locality-sensitive hashing scheme based on p-stable distributions.	Symposium on Computational Geometry	2004	DBLP DOI BibTeX RDF	p-stable distributions, locally sensitive hashing, sublinear algorithm, approximate nearest neighbor
1	Alex Brodsky, Faith Ellen Fich	Efficient synchronous snapshots.	PODC	2004	DBLP DOI BibTeX RDF	multiprocessor algorithms, shared memory objects
1	Kevin C. Zatloukal, Nicholas J. A. Harvey	Family trees: an ordered dictionary with optimal congestion, locality, degree, and search time.	SODA	2004	DBLP DOI BibTeX RDF
1	José Alberto Fernández-Zepeda, Daniel Fajardo-Delgado, José Antonio Cárdenas-Haro, Anu G. Bourgeois	Efficient Simulation of the Acyclic DR-Mesh on the LR-Mesh.	IPDPS	2004	DBLP DOI BibTeX RDF
1	Haibin Lu, Sartaj K. Sahni	Dynamic IP router-tables using highest-priority matching.	ISCC	2004	DBLP DOI BibTeX RDF
1	Haibin Lu, Sartaj Sahni	Enhanced Interval Trees for Dynamic IP Router-Tables.	IEEE Trans. Computers	2004	DBLP DOI BibTeX RDF	Interval trees, router tables, highest-priority matching, dynamic rule-tables, rule insertion and deletion, packet classification, packet routing, longest-prefix matching
1	Haibin Lu, Sartaj Sahni	O(log n) Dynamic Router-Tables for Prefixes and Ranges.	IEEE Trans. Computers	2004	DBLP DOI BibTeX RDF
1	Sartaj Sahni, Kun Suk Kim	An O(log n) Dynamic Router-Table Design.	IEEE Trans. Computers	2004	DBLP DOI BibTeX RDF	Packet routing, longest matching prefix, red-black trees
1	Hiroaki Kikuchi	Rabin Tree and Its Application to Group Key Distribution.	ATVA	2004	DBLP DOI BibTeX RDF
1	Jean G. Vaucher	Building Optimal Binary Search Trees from Sorted Values in O(N) Time.	Essays in Memory of Ole-Johan Dahl	2004	DBLP DOI BibTeX RDF	data structures, binary search tree, balanced trees
1	Brice Effantin	Generation of Unordered Binary Trees.	ICCSA	2004	DBLP DOI BibTeX RDF
1	Ka Wong Chong, Stavros D. Nikolopoulos, Leonidas Palios	An Optimal Parallel Co-Connectivity Algorithm.	Theory Comput. Syst.	2004	DBLP DOI BibTeX RDF
1	Amitava Datta	Multiple Addition and Prefix Sum on a Linear Array with a Reconfigurable Pipelined Bus System.	The Journal of Supercomputing	2004	DBLP DOI BibTeX RDF	pipelined bus, reconfigurable bus, matrix multiplication, addition, optical computing, prefix sum
1	Yijie Han	Optimal parallel selection.	SODA	2003	DBLP DOI BibTeX RDF	parallel algorithms, selection, EREW PRAM
1	Haim Kaplan, Eyal Molad, Robert Endre Tarjan	Dynamic rectangular intersection with priorities.	STOC	2003	DBLP DOI BibTeX RDF	rectangular intersection, rectangular point location, packet classification, orthogonal range searching
1	Haibin Lu, Sartaj Sahni	O(log n) Dynamic Router-Tables For Ranges.	ISCC	2003	DBLP DOI BibTeX RDF	dynamic router-tables, most-specific range matching, Packet routing, ranges
1	Mitali Singh, Viktor K. Prasanna	Energy-Optimal and Energy-Balanced Sorting in a Single-Hop Wireless Sensor Network.	PerCom	2003	DBLP DOI BibTeX RDF
1	Peter Z. Revesz, Yi Chen	Efficient Aggregation over Moving Objects. (PDF / PS)	TIME	2003	DBLP DOI BibTeX RDF
1	Gianni Franceschini, Roberto Grossi	Optimal Cache-Oblivious Implicit Dictionaries.	ICALP	2003	DBLP DOI BibTeX RDF
1	Ling Chen, Yi Pan	Faster Sorting on a Linear Array with a Reconfigurable Pipelined Bus System.	ISPA	2003	DBLP DOI BibTeX RDF
1	Stefan Dobrev	Communication-Efficient Broadcasting in Complete Networks with Dynamic Faults.	Theory Comput. Syst.	2003	DBLP DOI BibTeX RDF	Sense of Direction, Fault Tolerance, Distributed Computing, Broadcasting, Dynamic Faults, Complete Networks
1	Kim Miller, Suneeta Ramaswami, Peter Rousseeuw, Joan Antoni Sellarès, Diane L. Souvaine, Ileana Streinu, Anja Struyf	Efficient computation of location depth contours by methods of computational geometry.	Statistics and Computing	2003	DBLP DOI BibTeX RDF	bagplot, bivariate median, Tukey depth, robust estimation, graphical display
1	Jie Li, Yi Pan, Hong Shen	More Efficient Topological Sort Using Reconfigurable Optical Buses.	The Journal of Supercomputing	2003	DBLP DOI BibTeX RDF	time complexity, analysis of algorithms, massive parallelism, graph problem, optical bus
1	Amos Fiat, Jared Saia	Censorship resistant peer-to-peer content addressable networks.	SODA	2002	DBLP DOI BibTeX RDF
1	Miklós Ajtai, T. S. Jayram, Ravi Kumar, D. Sivakumar	Approximate counting of inversions in a data stream.	STOC	2002	DBLP DOI BibTeX RDF
1	Craig A. Lee, Eric Coe, Cauligi S. Raghavendra, J. Matt Clark, James Stepanek, Sameer Bhatia, Rohan Puri	Scalable Time Management Algorithms using Active Networks for Distributed Simulation.	DANCE	2002	DBLP DOI BibTeX RDF	distributed simulation, HLA, Active networks, time management
1	Gerth Stølting Brodal, Riko Jacob	Dynamic Planar Convex Hull.	FOCS	2002	DBLP DOI BibTeX RDF	Planar computational geometry, dynamic convex hull, finger searches, data structure, lower bound, search trees
1	Koji Nakano	An Optimal Randomized Ranking Algorithm on the k-channel Broadcast Communication Model. (PDF / PS)	ICPP	2002	DBLP DOI BibTeX RDF
1	Sartaj Sahni, Kun Suk Kim	O(log n) dynamic packet routing.	ISCC	2002	DBLP DOI BibTeX RDF	Packet routing, longest matching prefix, red-black trees
1	Wei Chen 0003, Koichi Wada	On Computing the Upper Envelope of Segments in Parallel.	IEEE Trans. Parallel Distrib. Syst.	2002	DBLP DOI BibTeX RDF	upper envelope, Davenport-Schinzel sequence, Computational geometry, visibility, convex hull, EREW PRAM model
1	Harold N. Gabow, San Skulrattanakulchai	Coloring Algorithms on Subcubic Graphs.	COCOON	2002	DBLP DOI BibTeX RDF
1	Walter Bachl	Semi-dynamic Orthogonal Drawings of Planar Graphs.	Graph Drawing	2002	DBLP DOI BibTeX RDF
1	Partha P. Goswami, Sandip Das, Subhas C. Nandy	Simplex Range Searching and k Nearest Neighbors of a Line Segment in 2D.	SWAT	2002	DBLP DOI BibTeX RDF
1	Sanguthevar Rajasekaran, Suneeta Ramaswami	Optimal Parallel Randomized Algorithms for the Voronoi Diagram of Line Segments in the Plane.	Algorithmica	2002	DBLP DOI BibTeX RDF
1	Amitava Datta	Efficient Graph-Theoretic Algorithms on a Linear Array with a Reconfigurable Pipelined Bus System.	The Journal of Supercomputing	2002	DBLP DOI BibTeX RDF	reconfigurable pipelined bus, minimum spanning forest, parallel algorithm, graph algorithms, connected components, optical computing, biconnected components
1	Ching Law, Amar K. Mehta, Kai-Yeung Siu	Performance of a new Bluetooth scatternet formation protocol.	MobiHoc	2001	DBLP DOI BibTeX RDF	ad hoc networks, Bluetooth, resource discovery, topology construction
1	Zvi Lotker, Boaz Patt-Shamir, David Peleg	Distributed MST for constant diameter graphs.	PODC	2001	DBLP DOI BibTeX RDF
1	Mikkel Thorup	Fully-dynamic min-cut.	STOC	2001	DBLP DOI BibTeX RDF
1	Timothy M. Chan	Dynamic planar convex hull operations in near-logarithmaic amortized time.	J. ACM	2001	DBLP DOI BibTeX RDF	computational geometry, convex hulls, dynamic data structures
1	Wey-Shiuan Hwang, Juyang Weng	Incremental hierarchical discriminating regression for indoor visual navigation.	ICIP	2001	DBLP DOI BibTeX RDF
1	Keqin Li, Victor Y. Pan	Parallel Matrix Multiplication on a Linear Array with a Reconfigurable Pipelined Bus System.	IEEE Trans. Computers	2001	DBLP DOI BibTeX RDF	Bilinear algorithm, optical pipelined bus, distributed memory system, matrix multiplication, speedup, PRAM, reconfigurable system, linear array, cost-optimality
1	Weifa Liang, Richard P. Brent, Hong Shen	Fully Dynamic Maintenance of k-Connectivity in Parallel.	IEEE Trans. Parallel Distrib. Syst.	2001	DBLP DOI BibTeX RDF	2-edge/vertex connectivity, 3-edge/vertex connectivity, parallel algorithm design and analysis, dynamic data structures, graph problems, NC algorithms
1	Biing-Feng Wang, Shan-Chyun Ku, Keng-Hua Shi	Cost-Optimal Parallel Algorithms for the Tree Bisector and Related Problems.	IEEE Trans. Parallel Distrib. Syst.	2001	DBLP DOI BibTeX RDF	Parallel algorithms, trees, EREW PRAM, location theory, bisectors, tree contraction, the Euler-tour technique
1	Mitica Craus	Parallel and Distributed Solutions for the Optimal Binary Search Tree Problem.	IWCC	2001	DBLP DOI BibTeX RDF
1	Ketan Mulmuley, Pradyut Shah	A Lower Bound for the Shortest Path Problem. (PDF / PS)	IEEE Conference on Computational Complexity	2000	DBLP DOI BibTeX RDF	parallel, lower bound, shortest path problem
1	Yi Pan, Si-Qing Zheng, Keqin Li, Hong Shen	Semigroup and Prefix Computations on Improved Generalized Mesh-Connected Computers with Multiple Buses. (PDF / PS)	IPDPS	2000	DBLP DOI BibTeX RDF	mesh-connected computer with multiple buses, parallel algorithm, parallel computing, parallel architecture, processor array, bus, mesh-connected computer
1	Raymond Greenlaw, Charles Shipley, James Wogulis	Fast Sequential and Parallel Algorithms for Label Selection to Obtain Space Efficient Implementations in a Software Configuration Management System.	PARELEC	2000	DBLP DOI BibTeX RDF