Lexbfs-ordering in asteroidal triple-free graphs

Jou Ming Chang, Chin Wen Ho, Ming Tat Ko

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

12 Scopus citations

Abstract

In this paper, we study the metric property of LexBFS- ordering on AT-free graphs. Based on a 2-sweep LexBFS algorithm, we show that every AT-free graph admits a vertex ordering, called the strong 2-cocomparability ordering, that for any three vertices u ≺ v ≺ w in the ordering, if d(u, w) ≤ 2 then d(u, v) = 1 or d(v, w) ≤ 2. As an application of this ordering, we provide a simple linear time recognition algorithm for bipartite permutation graphs, which form a subclass of AT-free graphs.

Original languageEnglish
Title of host publicationAlgorithms and Computation - 10th International Symposium, ISAAC 1999, Proceedings
EditorsC. Pandu Rangan, Alok Aggarwal
PublisherSpringer Verlag
Pages163-172
Number of pages10
ISBN (Print)3540669167, 9783540669166
DOIs
StatePublished - 1999
Event10th Annual International Symposium on Algorithms and Computation, ISAAC 1999 - Chennai, India
Duration: 16 Dec 199918 Dec 1999

Publication series

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

Conference

Conference10th Annual International Symposium on Algorithms and Computation, ISAAC 1999
Country/TerritoryIndia
CityChennai
Period16/12/9918/12/99

Fingerprint

Dive into the research topics of 'Lexbfs-ordering in asteroidal triple-free graphs'. Together they form a unique fingerprint.

Cite this