Cologne Excellence Cluster on Cellular Stress Responses in Aging Associated Diseases
computer science publication serverNot a member yet
819 research outputs found
Sort by
A simple MAX-CUT algorithm for planar graphs
No full textThe max-cut problem asks for partitioning the nodes V of a graph G=(V,E) into two sets (one of which might be empty), such that the sum of weights of edges joining nodes in different partitions is maximum. Whereas for general instances the max-cut problem is NP-hard, it is polynomially solvable for certain classes of graphs. For planar graphs, there exist several polynomial-time methods determining maximum cuts for arbitrary choice of edge weights. Typically, the problem is solved by computing a minimum-weight perfect matching in some associated graph. In this work, we present a new and simple algorithm for determining maximum cuts for arbitrary weighted planar graphs. Its running time can be bounded by O(|V|^(1.5)log|V|), similar to the fastest known methods. However, our transformation yields a much smaller associated graph than that of the known methods. Furthermore, it can be computed fast. As the practical running time strongly depends on the size of the associated graph, it can be expected that our algorithm is considerably faster than the methods known in the literature. More specifically, our program can determine maximum cuts in huge realistic and random planar graphs with up to 10^6 nodes
Characterizations of Restricted Pairs of Planar Graphs allowing Simultaneous Embeddings with Fixed Edges
No full textA set of planar graphs share a simultaneous embedding if they can be drawn on the same vertex set V in the Euclidean plane without crossings between edges of the same graph. Fixed edges are common edges between graphs that share the same simple curve in the simultaneous drawing. Determining in polynomial time which pairs of graphs share a simultaneous embedding with fixed edges (SEFE) has been open. We give a necessary and sufficient condition for whether a SEFE exists for pairs of graphs whose union is homeomorphic to K5 or K3,3 . This allows us to characterize the class of planar graphs that always have a SEFE with any other planar graph. We also characterize the class of biconnected outerplanar graphs that always have a SEFE with any other outerplanar graph. In both cases, we provide efficient algorithms to compute a SEFE. Finally, we provide a linear-time decision algorithm for deciding whether a pair of biconnected outerplanar graphs has a SEFE
On a relation between the domination number and a strongly connected bidirection of an undirected graph
No full textAs a generalization of directed and undirected graphs, Edmonds and Johnson introduced bidirected graphs. A bidirected graph is a graph each arc of which has either two positive end-vertices (tails), two negative end-vertices (heads), or one positive end-vertex (tail) and one negative end-vertex (head). We extend the notion of directed paths, distance, diameter and strong connectivity from directed to bidirected graphs and characterize those undirected graphs that allow a strongly connected bidirection. Considering the problem of finding the minimum diameter of all strongly connected bidirections of a given undirected graph, we generalize a result of Fomin et al. about directed graphs and obtain an upper bound for the minimum diameter which depends on the minimum size of a dominating set and the number of bridges in the undirected graph
Inferring Gene Regulatory Networks from Gene Expression Data
No full textGene regulatory networks describe how cells control the expression of genes, which, together with some additional regulation further downstream, determines the production of proteins essential for cellular function. The level of expression of each gene in the genome is modified by controlling whether and how vigorously it is transcribed to RNA, and subsequently translated to protein. RNA and protein expression will influence expression rates of other genes, thus giving rise to a complicated network structure. An analysis of regulatory processes within the cell will significantly further our understanding of cellular dynamics. It will shed light on normal and abnormal, diseased cellular events, and may provide information on pathways in dire diseases such as cancer. These pathways can provide information on how the disease develops, and what processes are involved in progression. Ultimately, we can hope that this will provide us with new therapeutic approaches and targets for drug design. It is thus no surprise that many efforts have been undertaken to reconstruct gene regulatory networks from gene expression measurements. In this chapter, we will provide an introductory overview over the field. In particular, we will present several different approaches to gene regulatory network inference, discuss their strengths and weaknesses, and provide guidelines on which models are appropriate under what circumstances. In addition, we sketch future developments and open problems
A Fast Exact Algorithm for the Optimum Cooperation Problem
No full textGiven a graph G=(V,E) with real edge weights, the optimum cooperation problem consists in determining a partition of the graph that maximizes the sum of weights of the edges having nodes in the same partition plus the number of resulting partitions. The problem is also known in the literature as the optimum attack problem in networks. It occurs as a subproblem in the separation of partition inequalities. Furthermore, a relevant physics application exists. Solution algorithms known in the literature require at least |V|-1 minimum cut computations in a corresponding network. In this work, we present a fast exact algorithm for the optimum cooperation problem. By graph-theoretic considerations and appropriately designed heuristics, we considerably reduce the number of minimum cut computations that are necessary in practice. We show the effectiveness of our method by comparing the performance of our algorithm with that of the fastest previously known method on instances coming from the physics application
A Simple 3-Approximation of Minimum Manhattan Networks
No full textGiven a set P of n points in the plane, a Manhattan network of P is a network that contains a rectilinear shortest path between every pair of points of P. A minimum Manhattan network of P is a Manhattan network of minimum total length. It is unknown whether it is NP-hard to construct a minimum Manhattan network. The best approximations published so far are a combinatorial 3-approximation algorithm in time O(n log n), and an LP-based 2-approximation algorithm. We present a new combinatorial 3-approximation for this problem in time O(n log n). Both our algorithm and its analysis are considerably simpler than the prior 3-approximation
A branch-and-cut approach to the crossing number problem
No full textThe crossing number of a graph is the minimum number of edge crossings in any drawing of the graph in the plane. Extensive research has produced bounds on the crossing number and exact formulae for special graph classes, yet the crossing numbers of graphs such as K_{11} or K_{9,11} are still unknown. Finding the crossing number is NP-hard for general graphs and no practical algorithm for its computation has been published so far. We present an integer linear programming formulation that is based on a reduction of the general problem to a restricted version of the crossing number problem in which each edge may be crossed at most once. We also present cutting plane generation heuristics and a column generation scheme. As we demonstrate in a computational study, a branch-and-cut algorithm based on these techniques as well as recently published preprocessing algorithms can be used to successfully compute the crossing number for small to medium sized general graphs
Identifying genes of gene regulatory networks using formal concept analysis
No full textIn order to understand the behavior of a gene regulatory network, it is essential to know the genes that belong to it. Identifying the correct members (e.g. in order to build a model) is a difficult task even for small subnetworks. Usually only few members of a network are known and one needs to guess the missing members based on experience or informed speculation. It is beneficial if one can additionally rely on experimental data to support this guess. In this work we present a new method based on formal concept analysis to detect unknown members of a gene regulatory network from gene expression time series data. We show that formal concept analysis is able to find a list of candidate genes for inclusion into a partially known basic network. This list can then be reduced by a statistical analysis so that the resulting genes interact strongly with the basic network and therefore should be included when modeling the network. The method has been applied to the DNA repair system of Mycobacterium tuberculosis. In this application our method produces comparable results to an already existing method of component selection while it is applicable to a broader range of problems
Modeling feedback loops in the H-NS-mediated regulationof the Escherichia coli bgl operon
No full textThe histone-like nucleoid-associated protein H-NS is a global transcriptional repressor that controls approximately 5% of all genes in {it Escherichia coli} and other Enterobacteria. H-NS binds to DNA with low specificity. Nonetheless, repression of some loci is exceptionally specific. Experimental data for the {it E.coli bgl} operon suggest that highly specific repression is caused by regulatory feedback mechanisms. To analyze whether such feedback mechanisms could account for the observed specificity of repression, a model was built based on expression data. The model includes three parameters of {it bgl} operon regulation. These are cooperativity of repression by binding of H-NS to two sites, an inverse correlation of the rate of repression by H-NS and the transcription rate, and a threshold for positive regulation by antiterminator BglG, which is encoded within the operon. The latter two parameters represent feedback loops in the model. The resulting system of equations was solved for the expression level of the operon and analyzed with respect to different promoter activities. The analysis demonstrated that the parameters included into the model are sufficient to simulate specific repression of {it bgl} by H-NS. Particularly, a small (3-fold) increase in the promoter activity resulted in a strong (80-fold) enhancement of {it bgl} operon expression. Moreover, analysis of the system's behavior for different conditions and parameter changes demonstrated that the model can exhibit hysteresis caused by the positive nonlinear feedback loop based on positive regulation by antiterminator BglG
Semi-Preemptive Routing on Trees
No full textWe study a variant of the pickup-and-delivery problem (PDP) in which the objects that have to be transported can be reloaded at most d times, for a given integer d. This problem is known to be polynomially solvable on paths or cycles and NP-complete on trees. We present a (4/3+epsilon)-approximation algorithm if the underlying graph is a tree. By using a result of Charikar et al. (1998), this can be extended to a O(log n log log n)-approximation for general graphs