Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings         Authors   Author's Info   Article details         Search    
LAYERWIDTH: Analysis of a New Metric for Directed Acyclic Graphs
Mark Hopkins
Abstract:
We analyze a new property of directed acyclic graphs (DAGs), called layerwidth, arising from a class of DAGs proposed by Eiter and Lukasiewicz. This class of DAGs permits certain problems of structural model-based causality and explanation to be tractably solved. In this paper, we first address an open question raised by Eiter and Lukasiewicz --- the computational complexity of deciding whether a given graph has a bounded layerwidth. After proving that this problem is NP-complete, we proceed by proving numerous important properties of layerwidth that are helpful in efficiently computing the optimal layerwidth. Finally, we compare this new DAG property to two other important DAG properties: treewidth and bandwidth
Keywords:
Pages: 321-328
PS Link:
PDF Link: /papers/03/p321-hopkins.pdf
BibTex:
@INPROCEEDINGS{Hopkins03,
AUTHOR = "Mark Hopkins ",
TITLE = "LAYERWIDTH: Analysis of a New Metric for Directed Acyclic Graphs",
BOOKTITLE = "Proceedings of the Nineteenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-03)",
PUBLISHER = "Morgan Kaufmann",
ADDRESS = "San Francisco, CA",
YEAR = "2003",
PAGES = "321--328"
}


hosted by DSL   •   site info   •   help