Worst-case analysis of the set-union problem with extended backtracking

DOI10.1016/0304-3975(89)90119-9zbMath0678.68035OpenAlexW1976070870WikidataQ59256059 ScholiaQ59256059MaRDI QIDQ1124334

Maurizio Talamo, Giorgio Gambosi, Giuseppe F. Italiano

Publication date: 1989

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(89)90119-9

zbMATH Keywords

backtrackingdata structureset-union problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial aspects of partitions of integers (05A17) Specification and verification (program logics, model checking, etc.) (68Q60) Discrete mathematics in relation to computer science (68R99)

Related Items (3)

A partially persistent data structure for the set-union problem ⋮ A note on set union with arbitrary deunions ⋮ The set union problem with dynamic weighted backtracking

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A class of algorithms which require nonlinear time to maintain disjoint sets
• The set union problem with dynamic weighted backtracking
• On the computational power of pushdown automata
• Organization and maintenance of large ordered indexes
• A partially persistent data structure for the set-union problem
• Amortized Computational Complexity
• On the Single-Operation Worst-Case Time Complexity of the Disjoint Set Union Problem
• Worst-case Analysis of Set Union Algorithms
• Efficiency of a Good But Not Linear Set Union Algorithm
• Amortized Analysis of Algorithms for Set Union with Backtracking
• Set Merging Algorithms
• Binary Search Trees of Bounded Balance

This page was built for publication: Worst-case analysis of the set-union problem with extended backtracking