Gray codes for AT-free orders via antimatroids

Jou Ming Chang; Ton Kloks; Hung Lung Wang

doi:10.1007/978-3-319-29516-9_7

Gray codes for AT-free orders via antimatroids

Jou Ming Chang, Ton Kloks, Hung Lung Wang^*

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

3 Citations (Scopus)

Abstract

The AT-free order is a linear order of the vertices of a graph the existence of which characterizes AT-free graphs. We show that all AT-free orders of an AT-free graph can be generated in O(1) amortized time.

Original language	English
Title of host publication	Combinatorial Algorithms - 26th International Workshop, IWOCA 2015, Revised Selected Papers
Editors	William F. Smyth, Zsuzsanna Liptak
Publisher	Springer Verlag
Pages	77-87
Number of pages	11
ISBN (Print)	9783319295152
DOIs	https://doi.org/10.1007/978-3-319-29516-9_7
Publication status	Published - 2016
Externally published	Yes
Event	26th International Workshop on Combinatorial Algorithms, IWOCA 2015 - Verona, Italy Duration: 2015 Oct 5 → 2015 Oct 7

Publication series

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

Conference

Conference	26th International Workshop on Combinatorial Algorithms, IWOCA 2015
Country/Territory	Italy
City	Verona
Period	2015/10/05 → 2015/10/07

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-319-29516-9_7

Cite this

Chang, J. M., Kloks, T., & Wang, H. L. (2016). Gray codes for AT-free orders via antimatroids. In W. F. Smyth, & Z. Liptak (Eds.), Combinatorial Algorithms - 26th International Workshop, IWOCA 2015, Revised Selected Papers (pp. 77-87). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9538). Springer Verlag. https://doi.org/10.1007/978-3-319-29516-9_7

Gray codes for AT-free orders via antimatroids. / Chang, Jou Ming; Kloks, Ton; Wang, Hung Lung.
Combinatorial Algorithms - 26th International Workshop, IWOCA 2015, Revised Selected Papers. ed. / William F. Smyth; Zsuzsanna Liptak. Springer Verlag, 2016. p. 77-87 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9538).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Chang, JM, Kloks, T & Wang, HL 2016, Gray codes for AT-free orders via antimatroids. in WF Smyth & Z Liptak (eds), Combinatorial Algorithms - 26th International Workshop, IWOCA 2015, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9538, Springer Verlag, pp. 77-87, 26th International Workshop on Combinatorial Algorithms, IWOCA 2015, Verona, Italy, 2015/10/05. https://doi.org/10.1007/978-3-319-29516-9_7

Chang JM, Kloks T, Wang HL. Gray codes for AT-free orders via antimatroids. In Smyth WF, Liptak Z, editors, Combinatorial Algorithms - 26th International Workshop, IWOCA 2015, Revised Selected Papers. Springer Verlag. 2016. p. 77-87. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-29516-9_7

Chang, Jou Ming ; Kloks, Ton ; Wang, Hung Lung. / Gray codes for AT-free orders via antimatroids. Combinatorial Algorithms - 26th International Workshop, IWOCA 2015, Revised Selected Papers. editor / William F. Smyth ; Zsuzsanna Liptak. Springer Verlag, 2016. pp. 77-87 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{fef141377a75496b82ce783b8096b3b1,

title = "Gray codes for AT-free orders via antimatroids",

abstract = "The AT-free order is a linear order of the vertices of a graph the existence of which characterizes AT-free graphs. We show that all AT-free orders of an AT-free graph can be generated in O(1) amortized time.",

author = "Chang, {Jou Ming} and Ton Kloks and Wang, {Hung Lung}",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2016.; 26th International Workshop on Combinatorial Algorithms, IWOCA 2015 ; Conference date: 05-10-2015 Through 07-10-2015",

year = "2016",

doi = "10.1007/978-3-319-29516-9_7",

language = "English",

isbn = "9783319295152",

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

publisher = "Springer Verlag",

pages = "77--87",

editor = "Smyth, {William F.} and Zsuzsanna Liptak",

booktitle = "Combinatorial Algorithms - 26th International Workshop, IWOCA 2015, Revised Selected Papers",

}

TY - GEN

T1 - Gray codes for AT-free orders via antimatroids

AU - Chang, Jou Ming

AU - Kloks, Ton

AU - Wang, Hung Lung

N1 - Publisher Copyright: © Springer International Publishing Switzerland 2016.

PY - 2016

Y1 - 2016

N2 - The AT-free order is a linear order of the vertices of a graph the existence of which characterizes AT-free graphs. We show that all AT-free orders of an AT-free graph can be generated in O(1) amortized time.

AB - The AT-free order is a linear order of the vertices of a graph the existence of which characterizes AT-free graphs. We show that all AT-free orders of an AT-free graph can be generated in O(1) amortized time.

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

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

U2 - 10.1007/978-3-319-29516-9_7

DO - 10.1007/978-3-319-29516-9_7

M3 - Conference contribution

AN - SCOPUS:84961205171

SN - 9783319295152

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

SP - 77

EP - 87

BT - Combinatorial Algorithms - 26th International Workshop, IWOCA 2015, Revised Selected Papers

A2 - Smyth, William F.

A2 - Liptak, Zsuzsanna

PB - Springer Verlag

T2 - 26th International Workshop on Combinatorial Algorithms, IWOCA 2015

Y2 - 5 October 2015 through 7 October 2015

ER -

Gray codes for AT-free orders via antimatroids

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this