Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/64491
Title: Forbidden induced subgraphs of normal Helly circular-arc graphs : characterization and detection
Authors: Cao, Y 
Grippo, LN
Safe, MD
Keywords: Certifying algorithms
Linear-time
(Proper) interval graphs
Chordal graphs
(Minimal) forbidden induced subgraphs
Holes
(Normal
Helly
proper) circular-arc models
Issue Date: 2017
Publisher: North-Holland
Source: Discrete applied mathematics, 2017, v. 216, no. Part 1, p. 67-83 How to cite?
Journal: Discrete applied mathematics 
Abstract: A normal Helly circular-arc graph is the intersection graph of a set of arcs on a circle of which no three or less arcs cover the whole circle. Lin et al. (2013) characterized circular-arc graphs that are not normal Helly circular-arc graphs, and used them to develop the first recognition algorithm for this graph class. As open problems, they ask for the forbidden subgraph characterization and a direct recognition algorithm for normal Helly circular-arc graphs, both of which are resolved by the current paper. Moreover, when the input is not a normal Helly circular-arc graph, our recognition algorithm finds in linear time a minimal forbidden induced subgraph as a certificate. Our approach yields also a considerably simpler algorithm for the certifying recognition of proper Helly circular-arc graphs, a subclass of normal Helly circular-arc graphs.
URI: http://hdl.handle.net/10397/64491
ISSN: 0166-218X
DOI: 10.1016/j.dam.2015.08.023
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

WEB OF SCIENCETM
Citations

1
Last Week
0
Last month
Citations as of Aug 14, 2017

Page view(s)

20
Last Week
3
Last month
Checked on Aug 13, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.