Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Publication Type
Articles 1 - 2 of 2
Full-Text Articles in Physical Sciences and Mathematics
A Linear-Time Recognition Algorithm For P4-Reducible Graphs, B. Jamison, S. Olariu
A Linear-Time Recognition Algorithm For P4-Reducible Graphs, B. Jamison, S. Olariu
Computer Science Faculty Publications
The P4-reducible graphs are a natural generalization of the well-known class of cographs, with applications to scheduling, computational semantics, and clustering. More precisely, the P4-reducible graphs are exactly the graphs none of whose vertices belong to more than one chordless path with three edges. 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.
On The Unique Tree Representation Of Graphs, Beverly Jamison
On The Unique Tree Representation Of Graphs, Beverly Jamison
Computer Science Theses & Dissertations
This dissertation investigates classes of graphs which admit tree representations unique up to isomorphism. The definitions of these classes are based on local properties of P4's, A template structure theorem is given which illustrates the nature of the local properties. The template theorem is instantiated for three different classes of graphs. Properties specific to each of the classes are used to produce a tree representation which can be used for graph computations, such as efficient resolution of graph isomorphism. Linear time algorithms for the recognition of three classes of graphs and for the construction of their tree representations …