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

DOI10.1016/0304-3975(89)90119-9MaRDI QIDQ1124334zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Giorgio Gambosi, Maurizio Talamo, 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

data structurebacktrackingset-union problem

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 4050989
• The Set Union Problem with Unlimited Backtracking
• scientific article; zbMATH DE number 3907792
• The set union problem with dynamic weighted backtracking
• Amortized Analysis of Algorithms for Set Union with Backtracking

Cites work

• scientific article; zbMATH DE number 3913653 (Why is no real title available?)
• scientific article; zbMATH DE number 3960991 (Why is no real title available?)
• scientific article; zbMATH DE number 4035134 (Why is no real title available?)
• scientific article; zbMATH DE number 4050989 (Why is no real title available?)
• scientific article; zbMATH DE number 3995082 (Why is no real title available?)
• A class of algorithms which require nonlinear time to maintain disjoint sets
• A partially persistent data structure for the set-union problem
• Amortized Analysis of Algorithms for Set Union with Backtracking
• Amortized Computational Complexity
• Binary Search Trees of Bounded Balance
• Efficiency of a Good But Not Linear Set Union Algorithm
• On the Single-Operation Worst-Case Time Complexity of the Disjoint Set Union Problem
• On the computational power of pushdown automata
• Organization and maintenance of large ordered indexes
• Set Merging Algorithms
• The set union problem with dynamic weighted backtracking
• Worst-case Analysis of Set Union Algorithms

Cited in

(12)

• scientific article; zbMATH DE number 3907792 (Why is no real title available?)
• A partially persistent data structure for the set-union problem
• scientific article; zbMATH DE number 3960991 (Why is no real title available?)
• scientific article; zbMATH DE number 4050989 (Why is no real title available?)
• The set union problem with dynamic weighted backtracking
• Backing up in singly linked lists
• Amortized Analysis of Algorithms for Set Union with Backtracking
• On the Single-Operation Worst-Case Time Complexity of the Disjoint Set Union Problem
• Worst case analysis of two heuristics for the set partitioning problem
• The Set Union Problem with Unlimited Backtracking
• Nested set union
• A note on set union with arbitrary deunions

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

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