Tree Decomposition with Applications to Constraint Processing
Abstract
This paper studies the possibility of removing redundant information from a given knowledge base and restructuring it in the form of a tree to enable efficient problem solving routines. We offer a novel approach that guarantees removal of all redundancies that hide a tree structure. We develop a polynomial-time algorithm that, given an arbitrary constraint network, either extracts (by edge removal) a precise tree representation from the path-consistent version of the network or acknowledges that no such tree cari be extracted. In the event of the latter, the tree generated may serve as a good approximation to the original network.
Cite
Text
Meiri et al. "Tree Decomposition with Applications to Constraint Processing." AAAI Conference on Artificial Intelligence, 1990.Markdown
[Meiri et al. "Tree Decomposition with Applications to Constraint Processing." AAAI Conference on Artificial Intelligence, 1990.](https://mlanthology.org/aaai/1990/meiri1990aaai-tree/)BibTeX
@inproceedings{meiri1990aaai-tree,
title = {{Tree Decomposition with Applications to Constraint Processing}},
author = {Meiri, Itay and Pearl, Judea and Dechter, Rina},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {1990},
pages = {10-16},
url = {https://mlanthology.org/aaai/1990/meiri1990aaai-tree/}
}