Average running time analysis of an algorithm to calculate the size of the union of Cartesian products.

DOI10.1016/S0012-365X(03)00239-5MaRDI QIDQ1417580zbMATH OpenOpenAlexFDO

Authors Susumu Suzuki, Toshihide Ibaraki

Publication date 5 January 2004

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(03)00239-5

zbMATH Keywords

Average running timeCartesian productSatisfiability problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 2188496
• Analysis of the total costs for variants of the union-find algorithm
• Worst-case Analysis of Set Union Algorithms
• Recognizing Cartesian products in linear time
• Amortized Analysis of Algorithms for Set Union with Backtracking
• A linear-time algorithm for a special case of disjoint set union
• Quasi-Linear-Time Algorithms by Generalisation of Union-Find in CHR
• Average-case analysis of algorithms using Kolmogorov complexity
• A simple expected running time analysis for randomized ``divide and conquer algorithms
• scientific article; zbMATH DE number 3907792

Cites work

• An Analysis of Backtracking with Search Rearrangement
• An Average Time Analysis of Backtracking
• CNF-Satisfiability Test by Counting and Polynomial Average Time
• Polynomial-average-time satisfiability problems

Cited in

(1)

• scientific article; zbMATH DE number 2188496 (Why is no real title available?)

This page was built for publication: Average running time analysis of an algorithm to calculate the size of the union of Cartesian products.

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