Premium
The linear arrangement problem on recursively constructed graphs
Author(s) -
Horton S. B.,
Easton T.,
Parker R. Gary
Publication year - 2003
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.10093
Subject(s) - computer science , combinatorics , mathematics , graph , discrete mathematics , time complexity
The linear arrangement problem on graphs is a relatively old and quite well‐known problem. Hard in general, it remains open on general recursive graphs (i.e., partial k ‐trees, etc.), which is somewhat frustrating since most hard graph problems are easily solved on recursive graphs. In this paper, we examine the linear arrangement problem with respect to these structures. Included are some negative (complexity) results as well as a solvable case. © 2003 Wiley Periodicals, Inc.