Algorithms and Complexity

The talk will concern compact, localized and distributed network representation methods. Traditional approaches to network representation are based on global data structures, which require access to the entire structure even if the sought information involves only a small and local set of entities. In contrast, localized network representation schemes are based on breaking the information into small local pieces, or labels, selected in a way that allows one to infer information regarding a small set of entities directly from their labels, without using any additional (global) information. The talk will concentrate mainly on combinatorial and algorithmic techniques, such as adjacency and distance labeling schemes and interval schemes for routing, and will cover a variety of complexity results. R. Petreschi et al. (Eds.): CIAC 2003, LNCS 2653, p. 1, 2003. c © Springer-Verlag Berlin Heidelberg 2003 Optimal Binary Search Trees with Costs Depending on the Access Paths Jayme L. Szwarcfiter Universidade Federal do Rio de Janeiro, RJ, Brasil Abstract. We describe algorithms for constructing optimal binary search trees, in which the access cost of a key depends on the k preceding keys, which were reached in the path to it. This problem has applications to searching on secondary memory and robotics. Two kinds of optimal trees are considered, namely optimal worst case trees and weighted average case trees. The time and space complexity of both algorithms are O(n) and O(n), respectively. The algorithms are based on a convenient decomposition and characterizations of sequences of keys, which are paths of special kinds in binary search trees. Finally, using generating functions, the exact number of steps performed by the algorithms has been calculated. The subject will be introduced by a general discussion on the construction of optimal binary search trees. We describe algorithms for constructing optimal binary search trees, in which the access cost of a key depends on the k preceding keys, which were reached in the path to it. This problem has applications to searching on secondary memory and robotics. Two kinds of optimal trees are considered, namely optimal worst case trees and weighted average case trees. The time and space complexity of both algorithms are O(n) and O(n), respectively. The algorithms are based on a convenient decomposition and characterizations of sequences of keys, which are paths of special kinds in binary search trees. Finally, using generating functions, the exact number of steps performed by the algorithms has been calculated. The subject will be introduced by a general discussion on the construction of optimal binary search trees. R. Petreschi et al. (Eds.): CIAC 2003, LNCS 2653, p. 2, 2003. c © Springer-Verlag Berlin Heidelberg 2003 On the Generation of Extensions of a Partially Ordered Set Jayme L. Szwarcfiter Universidade Federal do Rio de Janeiro, RJ, Brasil Abstract. A partially ordered set (or simply order) P is a set of elements E, together with a set R of relations of E, satisfying reflexivity, anti-symmetry and transitivity. The set E is called the ground set of P , while R is the relation set of it. There are many special orders. For example, when any two elements of E are related, the order is a chain. Similarly, we can define tree orders, forest orders and many others. An extension P ’ of P is an order P ’ having the same ground set as P , and such that its relation set contains R. When P ’ is a chain then P ’ is a linear extension of P . Similarly, when P ’ is a forest then it is a forest extension of P . We consider the algorithmic problem of generating all extensions of a given order and also extensions of a special kind. The subject will be introduced by a general discussion on partially ordered sets. A partially ordered set (or simply order) P is a set of elements E, together with a set R of relations of E, satisfying reflexivity, anti-symmetry and transitivity. The set E is called the ground set of P , while R is the relation set of it. There are many special orders. For example, when any two elements of E are related, the order is a chain. Similarly, we can define tree orders, forest orders and many others. An extension P ’ of P is an order P ’ having the same ground set as P , and such that its relation set contains R. When P ’ is a chain then P ’ is a linear extension of P . Similarly, when P ’ is a forest then it is a forest extension of P . We consider the algorithmic problem of generating all extensions of a given order and also extensions of a special kind. The subject will be introduced by a general discussion on partially ordered sets. R. Petreschi et al. (Eds.): CIAC 2003, LNCS 2653, p. 3, 2003. c © Springer-Verlag Berlin Heidelberg 2003 Error-Correcting Codes in Complexity Theory