๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Optimal one-page tree embeddings in linear time

โœ Scribed by Robert A. Hochberg; Matthias F. Stallmann

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
167 KB
Volume
87
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

โœฆ Synopsis

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(n 2.2 ) and O(n 1.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. 1

๐Ÿ“œ SIMILAR VOLUMES

Approximating Maximum Leaf Spanning Tree
Approximating Maximum Leaf Spanning Trees in Almost Linear Time
โœ Hsueh-I Lu; R Ravi ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 206 KB

Given an undirected graph, finding a spanning tree of the graph with the maximum number of leaves is MAX SNP-complete. In this paper we give a new greedy 3-approximation algorithm for maximum leaf spanning trees. The running ลฝลฝ . ลฝ .. time O m q n โฃ m, n required by our algorithm, where m is the num

On constrained infinite-time linear quad
On constrained infinite-time linear quadratic optimal control
โœ D. Chmielewski; V. Manousiouthakis ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 579 KB

This work presents a solution to the infinite-time linear quadratic optimal control (ITLQOC) problem with state and control constraints. It is shown that a single, finite dimensional, convex program of known size can yield this solution. Properties of the resulting value function, with respect to in

A linear-time algorithm for broadcast do
A linear-time algorithm for broadcast domination in a tree
โœ John Dabney; Brian C. Dean; Stephen T. Hedetniemi ๐Ÿ“‚ Article ๐Ÿ“… 2009 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 268 KB

## Abstract The broadcast domination problem is a variant of the classical minimum dominating set problem in which a transmitter of power __p__ at vertex __v__ is capable of dominating (broadcasting to) all vertices within distance __p__ from __v__. Our goal is to assign a broadcast power __f__(__v