@misc{HougardyWagler, author = {Hougardy, Stefan and Wagler, Annegret}, title = {Perfectness is an Elusive Graph Property}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6787}, number = {02-11}, abstract = {A graph property is called elusive (or evasive) if every algorithm for testing this property has to read in the worst case \$n\choose 2\$ entries of the adjacency matrix of the given graph. Several graph properties have been shown to be elusive, e.g. planarity (Best et al) or \$k\$-colorability (Bollobas). A famous conjecture of Karp says that every non-trivial monotone graph property is elusive. We prove that a non-monotone but hereditary graph property is elusive: perfectness.}, language = {en} } @misc{Rambau, author = {Rambau, J{\"o}rg}, title = {TOPCOM: Triangulations of Point Configurations and Oriented Matroids}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6849}, number = {02-17}, abstract = {TOPCOM is a package for computing triangulations of point configurations and oriented matroids. For example, for a point configuration one can compute the chirotope, components of the flip graph of triangulations, enumerate all triangulations. The core algorithms implemented in TOPCOM are described, and implentation issues are discussed.}, language = {en} } @misc{PfeifleRambau, author = {Pfeifle, Julian and Rambau, J{\"o}rg}, title = {Computing Triangulations Using Oriented Matroids}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6692}, number = {02-02}, abstract = {Oriented matroids are combinatorial structures that encode the combinatorics of point configurations. The set of all triangulations of a point configuration depends only on its oriented matroid. We survey the most important ingredients necessary to exploit oriented matroids as a data structure for computing all triangulations of a point configuration, and report on experience with an implementation of these concepts in the software package TOPCOM. Next, we briefly overview the construction and an application of the secondary polytope of a point configuration, and calculate some examples illustrating how our tools were integrated into the {\sc polymake} framework.}, language = {en} } @misc{GeerdesKarl, author = {Geerdes, Hans-Florian and Karl, Holger}, title = {The Potential of Relaying in Cellular Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7641}, number = {03-42}, abstract = {Relaying is a protocol extension for cellular wireless computer networks; in order to utilize radio resources more efficiently, several hops are allowed within one cell. This paper investigates the principle potential of relaying by casting transmission scheduling as a mathematical optimization problem, namely, a linear program. We analyze the throughput gains showing that, irrespective of the concrete scheduling algorithm, performance gains of up to 30\\% on average for concrete example networks are achievable.}, language = {en} } @misc{Geerdes, author = {Geerdes, Hans-Florian}, title = {Assessing Capacity Improvements by Relaying in Cellular Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7651}, number = {03-43}, abstract = {Relaying -- allowing multiple wireless hops -- is a protocol extension for cellular networks conceived to improve data throughput. Its benefits have only been quantified for small example networks. For assessing its general potential, we define a complex resource allocation\slash{}scheduling problem. Several mathematical models are presented for this problem; while a time-expanded MIP approach turns out intractable, a sophisticated column generation scheme leads to good computational results. We thereby show that for selected cases relaying can increase data throughput by 30\\% on the average.}, language = {en} } @misc{AbboudGroetschelKoch, author = {Abboud, Nadine and Gr{\"o}tschel, Martin and Koch, Thorsten}, title = {Mathematical Methods for Physical Layout of Printed Circuit Boards: An Overview}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9231}, number = {06-29}, abstract = {This article surveys mathematical models and methods used for physical PCB layout, i.e., component placement and wire routing. The main concepts are briefly described together with relevant references.}, language = {en} }