APPROXIMATING THE PATHWIDTH OF OUTERPLANAR GRAPHS

Authors
GOVINDAN R LANGSTON MA YAN XD
Citation
R. Govindan et al., APPROXIMATING THE PATHWIDTH OF OUTERPLANAR GRAPHS, Information processing letters, 68(1), 1998, pp. 17-23
Citations number
12
Categorie Soggetti
Computer Science Information Systems","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
68
Issue
1
Year of publication
1998
Pages
17 - 23
Database
ISI
SICI code
0020-0190(1998)68:1<17:ATPOOG>2.0.ZU;2-M
Abstract
Pathwidth is a well-known NP-complete graph metric. We present a techn ique to approximate the pathwidth of outerplanar graphs. Although a po lynomial-time algorithm is already known to determine the pathwidth of outerplanar graphs, this algorithm is not practical. Our algorithm wo rks in O(nlogn) time on graphs of order n, is practical and produces s olutions at most three times the optimum. (C) 1998 Elsevier Science B. V. All rights reserved.