Recognizing the \(P_ 4\)-structures of a tree (Q1343225)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Recognizing the \(P_ 4\)-structures of a tree |
scientific article |
Statements
Recognizing the \(P_ 4\)-structures of a tree (English)
0 references
1 February 1995
0 references
The \(P_ 4\)-structure of a graph \(G\) is the hypergraph having the same set of vertices as \(G\) and those 4-sets as hyperedges whose induced subgraph of \(G\) is a path. The paper presents a polynomial time algorithm detecting whether a given 4-uniform hypergraph is the \(P_ 4\)-structure of a tree, which is given in that case, or not. Non-isomorphic trees of the same order have the same \(P_ 4\)-struture iff both belong to a class of trees described in the paper.
0 references
\(P_ 4\)-structure
0 references
hypergraph
0 references
polynomial time algorithm
0 references
tree
0 references