Thumbnail
Access Restriction
Subscribed

Author Daz, Josep ♦ Petit, Jordi ♦ Serna, Maria
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2002
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Approximation algorithms ♦ Complexity ♦ Embedding ♦ Heuristics ♦ Layout ♦ Parameterized complexity ♦ Random graphs
Abstract Graph layout problems are a particular class of combinatorial optimization problems whose goal is to find a linear layout of an input graph in such way that a certain objective cost is optimized. This survey considers their motivation, complexity, approximation properties, upper and lower bounds, heuristics and probabilistic analysis on random graphs. The result is a complete view of the current state of the art with respect to layout problems from an algorithmic point of view.
ISSN 03600300
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2002-09-01
Publisher Place New York
e-ISSN 15577341
Journal ACM Computing Surveys (CSUR)
Volume Number 34
Issue Number 3
Page Count 44
Starting Page 313
Ending Page 356


Open content in new tab

   Open content in new tab
Source: ACM Digital Library