Article ID Journal Published Year Pages File Type
10332015 Information Processing Letters 2011 4 Pages PDF
Abstract
► We give a structural characterization of squares of strongly chordal split graphs. ► This implies a quadratic-time recognition algorithm for these graphs. ► Our results are of interest because recognizing squares of split graphs is hard. ► The complexity status of recognizing squares of strongly chordal graphs is unknown.
Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
A good characterization of squares of strongly chordal split graphs
Authors
, ,