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

DOI10.1016/0304-3975(89)90119-9zbMATH Open0678.68035DBLPjournals/tcs/GambosiIT89OpenAlexW1976070870WikidataQ59256059 ScholiaQ59256059MaRDI QIDQ1124334FDOQ1124334

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

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

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)

Cites Work

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

Cited In (12)

• On the Single-Operation Worst-Case Time Complexity of the Disjoint Set Union Problem
• Backing up in singly linked lists
• The Set Union Problem with Unlimited Backtracking
• Worst case analysis of two heuristics for the set partitioning problem
• Title not available (Why is that?)
• Amortized Analysis of Algorithms for Set Union with Backtracking
• Title not available (Why is that?)
• Title not available (Why is that?)
• A partially persistent data structure for the set-union problem
• The set union problem with dynamic weighted 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)