Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 2 of 2
Full-Text Articles in Computer Sciences
On The Structure Of Graphs With Few P4s, Luitpold Babel, Stephan Olariu
On The Structure Of Graphs With Few P4s, Luitpold Babel, Stephan Olariu
Computer Science Faculty Publications
We present new classes of graphs for which the isomorphism problem can be solved in polynomial time. These graphs are characterized by containing — in some local sense — only a small number of induced paths of length three. As it turns out, every such graph has a unique tree representation: the internal nodes correspond to three types of graph operations, while the leaves are basic graphs with a simple structure. The paper extends and generalizes known results about cographs, P4-reducible graphs, and P4-sparse graphs.
A Fast Parallel Algorithm To Recognize P4-Sparse Graphs, Rong Lin, Stephan Olariu
A Fast Parallel Algorithm To Recognize P4-Sparse Graphs, Rong Lin, Stephan Olariu
Computer Science Faculty Publications
A number of problems in mobile computing, group-based collaboration, automated theorem proving, networking, scheduling, and cluster analysis suggested the study of graphs featuring certain “local density” characteristics. Typically, the notion of local density is equated with the absence of chordless paths of length three or more. Recently, a new metric for local density has been proposed, allowing a number of such induced paths to occur. More precisely, a graphG is called P4-sparse if no set of five vertices inG induces more than one chordless path of length three. P4-sparse graphs generalize the well-known class of cographs corresponding to …