Recognizing the \(P_ 4\)-structures of a tree (Q1343225)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 716414
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Recognizing the \(P_ 4\)-structures of a tree |
scientific article; zbMATH DE number 716414 |
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
0.9165189
0 references
0.8933901
0 references
0.8913335
0 references
0.8816894
0 references
0.8797029
0 references
0 references
0.8705272
0 references
