Universität zu Köln

Le, Van Bang, Oversberg, Andrea and Schaudt, Oliver (2015). Polynomial time recognition of squares of Ptolemaic graphs and 3-sun-free split graphs. Theor. Comput. Sci., 602. S. 39 - 50. AMSTERDAM: ELSEVIER. ISSN 1879-2294

Full text not available from this repository.

Abstract

The square of a graph G, denoted G(2), is obtained from G by putting an edge between two distinct vertices whenever their distance is two. Then G is called a square root of G(2). Deciding whether a given graph has a square root is known to be NP-complete, even if the root is required to be a chordal graph or even a split graph. We present a polynomial time algorithm that decides whether a given graph has a Ptolemaic square root. If such a root exists, our algorithm computes one with a minimum number of edges. In the second part of our paper, we give a characterization of the graphs that admit a 3-sun-free split square root. This characterization yields a polynomial time algorithm to decide whether a given graph has such a root, and if so, to compute one. (C) 2015 Elsevier B.V. All rights reserved.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Le, Van Bang UNSPECIFIED UNSPECIFIED UNSPECIFIED Oversberg, Andrea UNSPECIFIED UNSPECIFIED UNSPECIFIED Schaudt, Oliver UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-389594
DOI:	10.1016/j.tcs.2015.07.060
Journal or Publication Title:	Theor. Comput. Sci.
Volume:	602
Page Range:	S. 39 - 50
Date:	2015
Publisher:	ELSEVIER
Place of Publication:	AMSTERDAM
ISSN:	1879-2294
Language:	English
Faculty:	Unspecified
Divisions:	Unspecified
Subjects:	no entry
Uncontrolled Keywords:	Keywords Language ROOTS; POWERS Multiple languages Computer Science, Theory & Methods Multiple languages
URI:	http://kups.ub.uni-koeln.de/id/eprint/38959