Optimal one-page tree embeddings in linear time
| Autor: | Matthias F. Stallmann, Robert Hochberg |
|---|---|
| Rok vydání: | 2003 |
| Předmět: |
Discrete mathematics
Class (set theory) Polynomial Graph theory Absolute value (algebra) Tree (graph theory) Computer Science Applications Theoretical Computer Science Combinatorics Signal Processing Topological graph theory Embedding Time complexity MathematicsofComputing_DISCRETEMATHEMATICS Information Systems Mathematics |
| Zdroj: | Information Processing Letters. 87:59-66 |
| ISSN: | 0020-0190 |
| DOI: | 10.1016/s0020-0190(03)00261-8 |
| Popis: | In the minimum linear arrangement problem one wishes to assign distinct integers to the vertices of a given graph so that the sum of the differences (in absolute value) across the edges of the graph is minimized. This problem is known to be NP-complete for the class of all graphs, but polynomial for trees algorithms of time complexity O(n2.2) and O(n1.6) were given by Shiloach [SIAM J. Comput. 8 (1979) 15-32] and Chung [Comput. Math. Appl. 10 (1984) 43-60], respectively. We present a linear-time algorithm for finding the optimal embedding (arrangement) in a restricted but important class of embeddings called one-page embeddings. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect