TY - GEN A1 - Koster, Arie M.C.A. A1 - Wagler, Annegret T1 - The extreme points of QSTAB(G) and its implications N2 - Perfect graphs constitute a well-studied graph class with a rich structure, reflected by many characterizations w.r.t different concepts. Perfect graphs are, e.g., characterized as precisely those graphs $G$ where the stable set polytope STAB$(G)$ coincides with the clique constraint stable set polytope QSTAB$(G)$. For all imperfect graphs STAB$(G) \subset$ QSTAB$(G)$ holds and, therefore, it is natural to measure imperfection in terms of the difference between STAB$(G)$ and QSTAB$(G)$. Several concepts have been developed in this direction, for instance the dilation ratio of STAB$(G)$ and QSTAB$(G)$ which is equivalent to the imperfection ratio imp$(G)$ of $G$. To determine imp$(G)$, both knowledge on the facets of STAB$(G)$ and the extreme points of QSTAB$(G)$ is required. The anti-blocking theory of polyhedra yields all {\em dominating} extreme points of QSTAB$(G)$, provided a complete description of the facets of STAB$(\overline G)$ is known. As this is typically not the case, we extend the result on anti-blocking polyhedra to a {\em complete} characterization of the extreme points of QSTAB$(G)$ by establishing a 1-1 correspondence to the facet-defining subgraphs of $\overline G$. We discuss several consequences, in particular, we give alternative proofs of several famous results. T3 - ZIB-Report - 06-30 KW - perfect graphs KW - imperfection ratio KW - stable set polytope Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9249 ER - TY - GEN A1 - Bodlaender, Hans L. A1 - Fomin, Fedor V. A1 - Koster, Arie M.C.A. A1 - Kratsch, Dieter A1 - Thilikos, Dimitrios M. T1 - On exact algorithms for treewidth N2 - We give experimental and theoretical results on the problem of computing the treewidth of a graph by exact exponential time algorithms using exponential space or using only polynomial space. We first report on an implementation of a dynamic programming algorithm for computing the treewidth of a graph with running time $O^\ast(2^n)$. This algorithm is based on the old dynamic programming method introduced by Held and Karp for the {\sc Tra veling Salesman} problem. We use some optimizations that do not affect the worst case running time but improve on the running time on actual instances and can be seen to be practical for small instances. However, our experiments show that the space use d by the algorithm is an important factor to what input sizes the algorithm is effective. For this purpose, we settle the problem of computing treewidth under the restriction that the space used is only polynomial. In this direction we give a simple $O^\ast(4^n)$ al gorithm that requires {\em polynomial} space. We also show that with a more complicated algorithm, using balanced separators, {\sc Treewidth} can be computed in $O^\ast(2.9512^n)$ time and polynomial space. T3 - ZIB-Report - 06-32 KW - treewidth KW - exponential algorithms Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9265 ER - TY - GEN A1 - Orlowski, Sebastian A1 - Koster, Arie M.C.A. A1 - Raack, Christian A1 - Wessäly, Roland T1 - Two-layer Network Design by Branch-and-Cut featuring MIP-based Heuristics N2 - This paper deals with MIP-based primal heuristics to be used within a branch-and-cut approach for solving multi-layer telecommunication network design problems. Based on a mixed-integer programming formulation for two network layers, we present three heuristics for solving important subproblems, two of which solve a sub-MIP. On multi-layer planning instances with many parallel logical links, we show the effectiveness of our heuristics in finding good solutions early in the branch-and-cut search tree. T3 - ZIB-Report - 06-47 KW - multi-layer network design KW - integer programming KW - branch-and-cut KW - heuristics Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9412 ER - TY - GEN A1 - Hülsermann, Ralf A1 - Jäger, Monika A1 - Koster, Arie M.C.A. A1 - Orlowski, Sebastian A1 - Wessäly, Roland A1 - Zymolka, Adrian T1 - Availability and Cost Based Evaluation of Demand-wise Shared Protection N2 - In this paper, we investigate the connection availabilities for the new protection scheme Demand-wise Shared Protection (DSP) and describe an appropriate approach for their computation. The exemplary case study on two realistic network scenarios shows that in most cases the availabilities for DSP are comparable with that for 1+1 path protection and better than in case of shared path protection. T3 - ZIB-Report - 06-15 KW - demand-wise shared protection KW - network availability KW - network optimization Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9080 ER -