Recognizing P4-extendible graphs in linear time

Hochstättler, Winfried and Schindler, Heike (1995) Recognizing P4-extendible graphs in linear time.
Technical Report , 13 p.


In a recent series of articles B. Jamison and S. Olariu introduced three classes of graphs with simple P4-structure. The well-known data structure of a cotree of a P4-free graph generalizes to these classes. We give a linear time algorithm to compute the parse tree for P4-extendible graphs.

Download: [img] Postscript
Download (204kB) | Preview
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Paper (Technical Report)
Citations: 1 (Google Scholar) |
Uncontrolled Keywords: P4-extendible graphs linear time algorithms modular tree
Divisions: Mathematical Institute
Related URLs:
Deposit Information:
ZAIK Number: zpr95-188
Depositing User: Winfried Hochstättler
Date Deposited: 13 Sep 2002 00:00
Last Modified: 19 Dec 2011 09:45