Cologne Excellence Cluster on Cellular Stress Responses in Aging Associated Diseases
computer science publication serverNot a member yet
819 research outputs found
Sort by
Lightness of digraphs in surfaces and directed game chromatic number
No full textThe lightness of a digraph is the minimum arc value, where the value of an arc is the maximum of the in-degrees of its terminal vertices. We determine upper bounds for the lightness of simple digraphs with minimum in-degree at least 1 (resp., graphs with minimum degree at least 2) and a given girth k, and without 4-cycles, which can be embedded in a surface S. (Graphs are considered as digraphs each arc having a parallel arc of opposite direction.) In case k is at least 5, these bounds are tight for surfaces of nonnegative Euler characteristics. This generalizes results of He et al. [11] concerning the lightness of planar graphs. From these bounds we obtain directly new bounds for the game coloring number, and thus for the game chromatic number of (di)graphs with girth k and without 4-cycles embeddable in S. The game chromatic resp. game coloring number were introduced by Bodlaender [3] resp Zhu [22] for graphs. We generalize these notions to arbitrary digraphs. We prove that the game coloring number of a directed simple forest is at most 3
Bilevel programming with discrete lower level problems
No full textIn this article we investigate bilevel programming problems with discrete lower level and continuous upper level problems. We will analyze the structure of these problems and discuss both the optimistic and the pessimistic solution approach. Since neither the optimistic nor the pessimistic solution functions are in general lower semicontinuous we introduce weak solution function. By using these functions we are able to discuss optimality conditions for local and global optimality
An SPQR-Tree Approach to Decide Special Cases of Simultaneous Embedding with Fixed Edges
No full textWe present a linear-time algorithm for solving the simulta- neous embedding problem with fixed edges (SEFE) for a planar graph and a pseudoforest (a graph with at most one cycle) by reducing it to the following embedding problem: Given a planar graph G, a cycle C of G, and a partitioning of the remaining vertices of G, does there exist a planar embedding in which the induced subgraph on each vertex partite of G C is contained entirely inside or outside C ? For the latter prob- lem, we present an algorithm that is based on SPQR-trees and has linear running time. We also show how we can employ SPQR-trees to decide SEFE for two planar graphs where one graph has at most two cycles and the intersection is a pseudoforest in linear time. These results give rise to our hope that our SPQR-tree approach might eventually lead to a polynomial-time algorithm for deciding the general SEFE problem for two planar graphs
Integer Flows with Multipliers 1 and 2
No full textThe problem to find a valid Integer generalized flow is long known to be NP-complete (S. Sahni, 1974). We show that the problem is still hard restricted to multipliers 1 and 2 and that optimal solutions with (almost) arbitrary fractions can occur. In some (still NP-hard) application motivated network instances optimal solutions are halfintegral. To solve the latter (optimally) we modify the Successive Shortest Path Algorithm and try to (heuristically) find acceptable integral solutions
Markov-Chain-Based Heuristics for the Minimum Feedback Vertex Set Problem
No full textLet G be a directed graph. A vertex set F is called feedback vertex set (FVS) if its removal from G results in an acyclic graph. Because determining a minimum cardinality FVS is known to be NP hard, [Karp72], one is interested in designing fast approximation algorithms determining near-optimum FVSs. The paper presents deterministic and randomised heuristics based on Markov chains. In this regard, an earlier approximation algorithm developed in [Speckenmeyer89] is revisited and refined. Experimental results demonstrate the overall performance superiority of our algorithms compared to other algorithms known from literature with respect to both criteria, the sizes of solutions determined, as well as the consumed runtimes
The incidence game chromatic number
No full textWe introduce the incidence game chromatic number which unifies the ideas of game chromatic number and incidence coloring number of an undirected graph. For k-degenerate graphs with maximum degree D, the upper bound 2D+4k-2 for the incidence game chromatic number is given. If D is at least 5k, we improve this bound to the value 2D+3k-1. We also determine the exact incidence game chromatic number of cycles, stars and sufficiently large wheels and obtain the lower bound 3D/2 for the incidence game chromatic number of graphs of maximum degree D
Horn representation of a concept lattice
No full textConcept lattices are the central notion of formal concept analysis. They are applied in
many different areas such as data mining, knowledge representation or ontology
engineering and are subject to ongoing research. In order to better understand the
nature of concept lattices, it is useful to consider their links to other mathematical
notions. For example, a concept lattice can be viewed as a special kind of poset or
closure system. In this paper, we consider another view of concept lattices by
establishing a link to propositional formulae and a special closure property of relations.
The main result is an elementary derivation of a Horn formula that uniquely represents
a concept lattice based on prime implicates. Using the derived Horn representation, we
re-establish the #P-completeness of the concept counting problem and find that the
Horn representation is closely related to the stem base of a concept lattice
Intersection Graphs in Simultaneous Embedding with Fixed Edges
No full textWe examine the simultaneous embedding with fixed edges problem for two planar graphs G1 and G2 with the focus on their in- tersection S := G1 ∩ G2 . In particular, we will present the complete set of intersection graphs S that guarantee a simultaneous embedding with fixed edges for (G1 , G2 ). More formally, we define the subset ISEFE of all planar graphs as follows: A graph S lies in ISEFE if every pair of pla- nar graphs (G1 , G2 ) with intersection S = G1 ∩ G2 has a simultaneous embedding with fixed edges. We will characterize this set by a detailed study of topological embeddings and finally give a complete list of graphs in this set as our main result of this paper
A Note on the Chromatic Number in Dense Graphs
No full textAlmost twenty years ago Reed conjectured that the arithmetic mean of a trivial lower bound, the clique number of a graph, and a trivial upper bound, the maximum degree of a graph plus one, establishes a new upper bound for the chromatic number of a graph. The conjecture is satisfied for a number of special graph classes, e.g. the conjecture has recently been proven by Rabern and by Kohl and Schiermeyer for the family of graphs with independence number two. For this family of dense graphs we present an alternative proof of Reed's Conjecture and generalize this result slightly