@inproceedings{6fd9cb9c75ff4b91af378532a69accbc,

title = "On vertex ranking for permutation and other graphs",

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.",

author = "Deogun, {J. S.} and T. Kloks and D. Kratsch and H. M{\"u}ller",

note = "Funding Information: This research was supported in part by the Office of Naval Research under Grant No. N0014-91-J-1693 and by DFGDeutsche Forschungsgemeinschaft under Kr 1371/1-1. Funding Information: Much work has been done in finding optimal rankings of trees. For trees there is now a linear time algorithm finding an optimal vertex ranking \[20\].F or the closely related edge ranking problem on trees an O(n 3) algorithm was given * This research was supported in part by the Office of Naval Research under Grant No. N0014-91-J-1693 and by Deutsche Forschungsgemeinschaft under Kr 1371/1-1. ** Currently under CHM contract at IRISA Rennes (France). Emaih kratsch@Lrisa.fr Publisher Copyright: {\textcopyright} 1994, Springer Verlag. All rights reserved.; Proceedings of the 11th Symposium on Theoretical Aspects of Computer Science (STACS'94) ; Conference date: 24-02-1994 Through 26-02-1994",

year = "1994",

doi = "10.1007/3-540-57785-8_187",

language = "English (US)",

isbn = "9783540577850",

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

publisher = "Springer Verlag",

pages = "747--758",

editor = "Patrice Enjalbert and Mayr, {Ernst W.} and Wagner, {Klaus W.}",

booktitle = "STACS 1994 - 11th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings",

}