Topological Parameters for Time-Space Tradeoff

2013/02/13 by Rina Dechter, Dechter, Rina · 1 citation
Computer Science · #AI-based Problem Solving and Planning #Artificial Intelligence (cs.AI) #Bayesian Modeling and Causal Inference #Constraint Satisfaction and Optimization #FOS: Computer and information sciences #cs.AI

paper · pdf · doi:10.48550/arxiv.1302.3573

Appears in Proceedings of the Twelfth Conference on Uncertainty in Artificial Intelligence (UAI1996)

arxiv created 2013/02/13 · openalex publication_date 2013/02/13 · arxiv updated 2013/02/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper we propose a family of algorithms combining tree-clustering with conditioning that trade space for time. Such algorithms are useful for reasoning in probabilistic and deterministic networks as well as for accomplishing optimization tasks. By analyzing the problem structure it will be possible to select from a spectrum the algorithm that best meets a given time-space specification.

Citations

• An Evaluation of Structural Parameters for Probabilistic Reasoning: Results on Benchmark Circuits
• Graphical Models for Preference and Utility

Cited by

• An Evaluation of Structural Parameters for Probabilistic Reasoning: Results on Benchmark Circuits
• Evaluation of Bayesian networks with flexible state-space abstraction methods
• Resolution versus Search: Two Strategies for SAT

Related

• Improved Space-efficient Linear Time Algorithms for Some Classical Graph Problems
• Temporal Clustering
• Time and space complexity of deterministic and nondeterministic decision trees
• Sketching semidefinite programs for faster clustering
• Clustering Based on Pairwise Distances When the Data is of Mixed Dimensions