Direct and certifying recognition of normal helly circular-arc graphs in linear time

Yixin Cao

doi:10.1007/978-3-319-08016-1_2

Direct and certifying recognition of normal helly circular-arc graphs in linear time

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

1 Citation (Scopus)

Abstract

A normal Helly circular-arc graph is the intersection graph of arcs on a circle of which no three or less arcs cover the whole circle. Lin et al. [Discrete Appl. Math. 2013] presented the first recognition algorithm for this graph class by characterizing circular-arc graphs that are not in it. They posed as an open problem to design a direct recognition algorithm, which is resolved by the current paper. When the input is not a normal Helly circular-arc graph, our algorithm finds in linear time a minimal forbidden induced subgraph. Grippo and Safe [arXiv:1402.2641] recently reported the forbidden induced subgraphs characterization of normal Helly circular-arc graphs. The correctness proof of our algorithm provides, as a byproduct, an alternative proof to this characterization.

Original language	English
Title of host publication	Frontiers in Algorithmics - 8th International Workshop, FAW 2014, Proceedings
Publisher	Springer Verlag
Pages	13-24
Number of pages	12
ISBN (Print)	9783319080154
DOIs	https://doi.org/10.1007/978-3-319-08016-1_2
Publication status	Published - 1 Jan 2014
Event	8th International Frontiers of Algorithmics Workshop, FAW 2014 - Zhangjiajie, China Duration: 28 Jun 2014 → 30 Jun 2014

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8497 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	8th International Frontiers of Algorithmics Workshop, FAW 2014
Country/Territory	China
City	Zhangjiajie
Period	28/06/14 → 30/06/14

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

More information

10.1007/978-3-319-08016-1_2

Cite this

Cao, Y. (2014). Direct and certifying recognition of normal helly circular-arc graphs in linear time. In Frontiers in Algorithmics - 8th International Workshop, FAW 2014, Proceedings (pp. 13-24). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8497 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-08016-1_2

@inproceedings{94caad13c32043e6bba5bddb5ea813ab,

title = "Direct and certifying recognition of normal helly circular-arc graphs in linear time",

abstract = "A normal Helly circular-arc graph is the intersection graph of arcs on a circle of which no three or less arcs cover the whole circle. Lin et al. [Discrete Appl. Math. 2013] presented the first recognition algorithm for this graph class by characterizing circular-arc graphs that are not in it. They posed as an open problem to design a direct recognition algorithm, which is resolved by the current paper. When the input is not a normal Helly circular-arc graph, our algorithm finds in linear time a minimal forbidden induced subgraph. Grippo and Safe [arXiv:1402.2641] recently reported the forbidden induced subgraphs characterization of normal Helly circular-arc graphs. The correctness proof of our algorithm provides, as a byproduct, an alternative proof to this characterization.",

author = "Yixin Cao",

year = "2014",

month = jan,

day = "1",

doi = "10.1007/978-3-319-08016-1_2",

language = "English",

isbn = "9783319080154",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "13--24",

booktitle = "Frontiers in Algorithmics - 8th International Workshop, FAW 2014, Proceedings",

address = "Germany",

note = "8th International Frontiers of Algorithmics Workshop, FAW 2014 ; Conference date: 28-06-2014 Through 30-06-2014",

}

Cao, Y 2014, Direct and certifying recognition of normal helly circular-arc graphs in linear time. in Frontiers in Algorithmics - 8th International Workshop, FAW 2014, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8497 LNCS, Springer Verlag, pp. 13-24, 8th International Frontiers of Algorithmics Workshop, FAW 2014, Zhangjiajie, China, 28/06/14. https://doi.org/10.1007/978-3-319-08016-1_2

Direct and certifying recognition of normal helly circular-arc graphs in linear time. / Cao, Yixin.
Frontiers in Algorithmics - 8th International Workshop, FAW 2014, Proceedings. Springer Verlag, 2014. p. 13-24 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8497 LNCS).

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

TY - GEN

T1 - Direct and certifying recognition of normal helly circular-arc graphs in linear time

AU - Cao, Yixin

PY - 2014/1/1

Y1 - 2014/1/1

N2 - A normal Helly circular-arc graph is the intersection graph of arcs on a circle of which no three or less arcs cover the whole circle. Lin et al. [Discrete Appl. Math. 2013] presented the first recognition algorithm for this graph class by characterizing circular-arc graphs that are not in it. They posed as an open problem to design a direct recognition algorithm, which is resolved by the current paper. When the input is not a normal Helly circular-arc graph, our algorithm finds in linear time a minimal forbidden induced subgraph. Grippo and Safe [arXiv:1402.2641] recently reported the forbidden induced subgraphs characterization of normal Helly circular-arc graphs. The correctness proof of our algorithm provides, as a byproduct, an alternative proof to this characterization.

AB - A normal Helly circular-arc graph is the intersection graph of arcs on a circle of which no three or less arcs cover the whole circle. Lin et al. [Discrete Appl. Math. 2013] presented the first recognition algorithm for this graph class by characterizing circular-arc graphs that are not in it. They posed as an open problem to design a direct recognition algorithm, which is resolved by the current paper. When the input is not a normal Helly circular-arc graph, our algorithm finds in linear time a minimal forbidden induced subgraph. Grippo and Safe [arXiv:1402.2641] recently reported the forbidden induced subgraphs characterization of normal Helly circular-arc graphs. The correctness proof of our algorithm provides, as a byproduct, an alternative proof to this characterization.

UR - http://www.scopus.com/inward/record.url?scp=84903558234&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-08016-1_2

DO - 10.1007/978-3-319-08016-1_2

M3 - Conference article published in proceeding or book

SN - 9783319080154

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 13

EP - 24

BT - Frontiers in Algorithmics - 8th International Workshop, FAW 2014, Proceedings

PB - Springer Verlag

T2 - 8th International Frontiers of Algorithmics Workshop, FAW 2014

Y2 - 28 June 2014 through 30 June 2014

ER -

Cao Y. Direct and certifying recognition of normal helly circular-arc graphs in linear time. In Frontiers in Algorithmics - 8th International Workshop, FAW 2014, Proceedings. Springer Verlag. 2014. p. 13-24. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-08016-1_2

Direct and certifying recognition of normal helly circular-arc graphs in linear time

Abstract

Publication series

Conference

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this