Paper Info
Title
Computing square roots of trivially perfect and threshold graphs
Abstract
A graph H is a square root of a graph G if two vertices are adjacent in G if and only if they are at distance one or two in H. Computing a square root of a given graph is NP-hard, even when the input graph is restricted to be chordal. In this paper, we show that computing a square root can be done in linear time for a well-known subclass of chordal graphs, the class of trivially perfect graphs. This result is obtained by developing a structural characterization of graphs that have a split square root. We also develop linear time algorithms for determining whether a threshold graph given either by a degree sequence or by a separating structure has a square root.
Year
DOI
Venue
2013
10.1016/j.dam.2012.12.027
Discrete Applied Mathematics
Keywords
DocType
Volume
threshold graph,linear time algorithm,trivially perfect graph,computing square root,split square root,square root,graph g,linear time,graph h,chordal graph,input graph,split graph
Journal
161
Issue
ISSN
Citations 
10-11
0166-218X
14
PageRank 
References 
Authors
0.70
30
2
Name
Order
Citations
PageRank
Martin Milanič124229.49
Oliver Schaudt29521.74