Efficiently recognizing the P4-structure of trees and of bipartite graphs without short cycles

被引：3

作者：

Brandstädt, A ^{[1
]}

Le, VB

Olariu, S

机构：

[1] Univ Rostock, FB Informat, D-18051 Rostock, Germany

[2] Old Dominion Univ, Dept Comp Sci, Norfolk, VA 23529 USA

来源：

GRAPHS AND COMBINATORICS | 2000年 / 16卷 / 04期

关键词：

Running Time; Bipartite Graph; Efficient Algorithm; Short Cycle; Good Running;

D O I：

10.1007/s003730070002

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A 4-uniform hypergraph represents the P-4-structure of a graph G if its hyperedges are the vertex sets of the P-4's in G. By using the weighted 2-section graph of the hypergraph we propose a simple efficient algorithm to decide whether a given 4-uniform hypergraph represents the P-4-structure of a bipartite graph without 4-cycle and 6-cycle. For trees, our algorithm is different from that given by G. Ding and has a better running time namely O(n(2)) where n is the number of vertices.

引用

页码：381 / 387

页数：7