Finding a Sun in Building-Free Graphs

Deciding whether an arbitrary graph contains a sun was recently shown to be NP-complete (Hoàng in SIAM J Discret Math 23:2156–2162, 2010 ). We show that whether a building-free graph contains a sun can be decided in O(min{ mn 3 , m 1.5 n 2 }) time and, if a sun exists, it can be found in the same ti...

Full description

Saved in:
Bibliographic Details
Published in:Graphs and combinatorics 2012-05, Vol.28 (3), p.347-364
Main Authors: Eschen, Elaine M., Hoàng, Chính T., Spinrad, Jeremy P., Sritharan, R.
Format: Article
Language:English
Subjects:
Algorithms
Combinatorial analysis
Combinatorics
Constrictions
Construction
Engineering Design
Graphs
Mathematics
Mathematics and Statistics
Original Paper
Parity
Sun
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Deciding whether an arbitrary graph contains a sun was recently shown to be NP-complete (Hoàng in SIAM J Discret Math 23:2156–2162, 2010 ). We show that whether a building-free graph contains a sun can be decided in O(min{ mn 3 , m 1.5 n 2 }) time and, if a sun exists, it can be found in the same time bound. The class of building-free graphs contains many interesting classes of perfect graphs such as Meyniel graphs which, in turn, contains classes such as hhd-free graphs, i-triangulated graphs, and parity graphs. Moreover, there are imperfect graphs that are building-free. The class of building-free graphs generalizes several classes of graphs for which an efficient test for the presence of a sun is known. We also present a vertex elimination scheme for the class of (building, gem)-free graphs. The class of (building, gem)-free graphs is a generalization of the class of distance hereditary graphs and a restriction of the class of (building, sun)-free graphs.
ISSN:0911-0119
1435-5914
DOI:10.1007/s00373-011-1047-9