Efficient splitting and merging algorithms for order decomposable problems

DOI10.1007/3-540-63165-8_215MaRDI QIDQ4571990zbMATH OpenOpenAlexFDO

Authors Roberto Grossi, Giuseppe F. Italiano

Publication date 4 July 2018

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-63165-8_215

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Data structures (68P05) Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Efficient splitting and merging algorithms for order decomposable problems.
• Concatenable structures for decomposable problems
• Concatenable segment trees (extended abstract)
• Data structures for mergeable trees
• Priority Search Trees

Cites work

• A linear-time algorithm for computing the Voronoi diagram of a convex polygon
• Adding range restriction capability to dynamic data structures
• Concatenable structures for decomposable problems
• Decomposable searching problems
• Decomposable searching problems I. Static-to-dynamic transformation
• Divided \(k-d\) trees
• Dynamic multi-dimensional data structures based on quad- and k-d trees
• Dynamization of order decomposable set problems
• General methods for adding range restrictions to decomposable searching problems
• scientific article; zbMATH DE number 3887061 (Why is no real title available?)
• scientific article; zbMATH DE number 3716801 (Why is no real title available?)
• scientific article; zbMATH DE number 3716802 (Why is no real title available?)
• scientific article; zbMATH DE number 3722116 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• Lower bounds on the efficiency of transforming static data structures into dynamic structures
• Maintenance of configurations in the plane
• Multidimensional binary search trees used for associative searching
• Optimal dynamization of decomposable searching problems
• Optimal External Memory Interval Management
• Organization and maintenance of large ordered indexes
• Quad trees: A data structure for retrieval by composite keys
• Some principles for dynamizing decomposable searching problems
• The design of dynamic data structures
• Union-copy structures and dynamic segment trees
• Worst-case optimal insertion and deletion methods for decomposable searching problems

Cited in

(4)

• Some optimal algorithms for decomposed partially ordered sets
• Concatenable structures for decomposable problems
• Efficient splitting and merging algorithms for order decomposable problems.
• Sequential-Merge Facets for Two-Dimensional Group Problems

This page was built for publication: Efficient splitting and merging algorithms for order decomposable problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4571990)