Layerwidth: Analysis of a New Metric for Directed Acyclic Graphs
Abstract
We analyze a new property of directed acyclic graphs (DAGs), called layerwidth, arising from a useful class of DAGs proposed by Eiter and Lukasiewicz for tractable causal reasoning. First, we establish that the complexity of deciding whether a given graph has a bounded layerwidth is NP-complete. Then we proceed to prove key 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.
Cite
Text
Hopkins. "Layerwidth: Analysis of a New Metric for Directed Acyclic Graphs." Conference on Uncertainty in Artificial Intelligence, 2003.Markdown
[Hopkins. "Layerwidth: Analysis of a New Metric for Directed Acyclic Graphs." Conference on Uncertainty in Artificial Intelligence, 2003.](https://mlanthology.org/uai/2003/hopkins2003uai-layerwidth/)BibTeX
@inproceedings{hopkins2003uai-layerwidth,
title = {{Layerwidth: Analysis of a New Metric for Directed Acyclic Graphs}},
author = {Hopkins, Mark},
booktitle = {Conference on Uncertainty in Artificial Intelligence},
year = {2003},
pages = {321-328},
url = {https://mlanthology.org/uai/2003/hopkins2003uai-layerwidth/}
}