Efficiently recognizing the \(P_4\)-structure of trees and of bipartite graphs without short cycles (Q5935599)
From MaRDI portal
scientific article; zbMATH DE number 1610693
Language | Label | Description | Also known as |
---|---|---|---|
English | Efficiently recognizing the \(P_4\)-structure of trees and of bipartite graphs without short cycles |
scientific article; zbMATH DE number 1610693 |
Statements
Efficiently recognizing the \(P_4\)-structure of trees and of bipartite graphs without short cycles (English)
0 references
2000
0 references
The \(P_4\)-structure of a graph \(G\) is a 4-uniform hypergraph whose vertex set coincides with the vertex set of \(G\) and whose edge set consists of quadruples of vertices that form induced 4-vertex paths in \(G\). The authors propose a simple algorithm deciding if an input 4-uniform hypergraph is a \(P_4\)-structure of a bipartite graph without cycles of length 4 and 6. The running time of the algorithm is quadratic with respect to the number of vertices of the input hypergraph. In the special case of trees the algorithm has a better running time than other algorithms known to date.
0 references
bipartite graph
0 references
perfect graph
0 references
uniform hypergraph
0 references
\(P_4\)-structure
0 references
paths
0 references
cycles
0 references
algorithm
0 references
trees
0 references