Open AccessA linear-time recognition algorithm for P 4-reducible graphs
Author(s) -
B. Jamison,
Stephan Olariu
Publication year - 1989
Publication title -
lecture notes in computer science
Language(s) - English
Resource type - Book series
SCImago Journal Rank - 0.249
H-Index - 400
eISSN - 1611-3349
pISSN - 0302-9743
DOI - 10.1007/3-540-52048-1_28
Subject(s) - chordal graph , combinatorics , computer science , indifference graph , time complexity , class (philosophy) , isomorphism (crystallography) , representation (politics) , metric dimension , path (computing) , discrete mathematics , longest path problem , graph isomorphism , tree (set theory) , mathematics , graph , 1 planar graph , artificial intelligence , line graph , programming language , chemistry , politics , political science , crystal structure , law , crystallography
P4-reducible graphs are precisely the graphs none of whose vertices belong to more than one chordless path with three edges. As it turns out, the class of P4-reducible graphs strictly contains the well-known class of cographs. A remarkable property of P4-reducible graphs is their unique tree representation up to isomorphism. In this paper we present a linear-time algorithm to recognize P4-reducible graphs and to construct their corresponding tree representation.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom