A simple algorithm to construct a consistent extension of a partially oriented graph

@techreport{dor1992pdagextension, abstract = {A Partially directed acyclic graph, (pdag), is a graph which contains both directed and undirected edges, with no directed cycle in its directed subgraph. An oriented extension of a pdag G is a fully directed acyclic graph (dag) on the same underlying set of edges, with the same orientation on the directed subgraph ofG and the same set of vee-structures. A vee-structure is formed by two edges, directed toward a common head, while their tails are nonadjacent. A simple polynomial-time algorithm is presented, to solve the following problem: Given a pdag, does it admit an oriented extension? The problem was stated by Verma and Pearl, while studying the existence of causal explanation to a given set of observed independencies. '}, address = {Los Angeles, CA, USA}, author = {Dor, Dorit and Tarsi, Michael }, citeulike-article-id = {2984550}, institution = {Cognitive Systems Laboratory, Computer Science Department, University of California}, keywords = {pdag}, month = {October}, number = {R-185}, posted-at = {2008-07-10 11:36:43}, priority = {2}, title = {A simple algorithm to construct a consistent extension of a partially oriented graph}, year = {1992} }

TY - RPRT ID - dor1992pdagextension L3 - citeulike-article-id:2984550 TI - A simple algorithm to construct a consistent extension of a partially oriented graph IS - R-185 AD - Los Angeles, CA, USA N2 - A Partially directed acyclic graph, (pdag), is a graph which contains both directed and undirected edges, with no directed cycle in its directed subgraph. An oriented extension of a pdag G is a fully directed acyclic graph (dag) on the same underlying set of edges, with the same orientation on the directed subgraph ofG and the same set of vee-structures. A vee-structure is formed by two edges, directed toward a common head, while their tails are nonadjacent. A simple polynomial-time algorithm is presented, to solve the following problem: Given a pdag, does it admit an oriented extension? The problem was stated by Verma and Pearl, while studying the existence of causal explanation to a given set of observed independencies. ' KW - pdag AU - Dor, Dorit AU - Tarsi, Michael PY - 1992/10// ER -