On vertex ranking for permutation and other graphs

J. S. Deogun, T. Kloks, D. Kratsch, H. Müller

Research output: Chapter in Book/Report/Conference proceedingConference contribution

46 Scopus citations

Abstract

In this paper we show that an optimal vertex ranking of a permutation graph can be computed in time O(n6), where n is the number of vertices. The demonstrated minimal separator approach can also be used for designing polynomial time algorithms computing an optimal vertex ranking on the following classes of well-structured graphs: circular permutation graphs, interval graphs, circular arc graphs, trapezoid graphs and cocomparability graphs of bounded dimension.

Original languageEnglish (US)
Title of host publicationSTACS 1994 - 11th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings
EditorsPatrice Enjalbert, Ernst W. Mayr, Klaus W. Wagner
PublisherSpringer Verlag
Pages747-758
Number of pages12
ISBN (Print)9783540577850
DOIs
StatePublished - 1994
EventProceedings of the 11th Symposium on Theoretical Aspects of Computer Science (STACS'94) - Caen, Fr
Duration: Feb 24 1994Feb 26 1994

Publication series

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

Other

OtherProceedings of the 11th Symposium on Theoretical Aspects of Computer Science (STACS'94)
CityCaen, Fr
Period2/24/942/26/94

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'On vertex ranking for permutation and other graphs'. Together they form a unique fingerprint.

Cite this