Search

Given a graph $$G=(V, E)$$ , a $$P_2$$ - packing $$\mathcal {P}$$ is a collection of vertex disjoint copies of $$P_2$$ s in $$G$$ where a $$P_2$$ is a simple path with three vertices and two edges. The Maximum $$P_2$$ - Packing problem is to find a $$P_2$$ -packing $$\mathcal {P}$$ in the input graph $$G$$ of maximum cardinality. This problem is NP-hard for cubic graphs. In this paper, we give a branch-and-reduce algorithm for the Maximum $$P_2$$ - Packing problem in cubic graphs. We analyze the running time of the algorithm using measure-and-conquer and show that it runs in time $$O^{*}(1.4366^n)$$ which is faster than previous known exact algorithms where $$n$$ is the number of vertices in the input graph. [ABSTRACT FROM AUTHOR]

Background: Mathematical modeling has been applied to the study and analysis of complex biological systems for a long time. Some processes in biological systems, such as the gene expression and feedback control in signal transduction networks, involve a time delay. These systems are represented as delay differential equation (DDE) models. Numerical sensitivity analysis of a DDE model by the direct method requires the solutions of model and sensitivity equations with time-delays. The major effort is the computation of Jacobian matrix when computing the solution of sensitivity equations. The computation of partial derivatives of complex equations either by the analytic method or by symbolic manipulation is time consuming, inconvenient, and prone to introduce human errors. To address this problem, an automatic approach to obtain the derivatives of complex functions efficiently and accurately is necessary. Results: We have proposed an efficient algorithm with an adaptive step size control to compute the solution and dynamic sensitivities of biological systems described by ordinal differential equations (ODEs). The adaptive direct-decoupled algorithm is extended to solve the solution and dynamic sensitivities of time-delay systems describing by DDEs. To save the human effort and avoid the human errors in the computation of partial derivatives, an automatic differentiation technique is embedded in the extended algorithm to evaluate the Jacobian matrix. The extended algorithm is implemented and applied to two realistic models with time-delays: the cardiovascular control system and the TNF-α signal transduction network. The results show that the extended algorithm is a good tool for dynamic sensitivity analysis on DDE models with less user intervention. Conclusions: By comparing with direct-coupled methods in theory, the extended algorithm is efficient, accurate, and easy to use for end users without programming background to do dynamic sensitivity analysis on complex biological systems with time-delays. [ABSTRACT FROM AUTHOR]

Abstract: Given a class of graphs , a graph is a probe graph of if its vertices can be partitioned into two sets, , the probes, and an independent set , the nonprobes, such that can be embedded into a graph of by adding edges between certain vertices of . If the partition of the vertices into probes and nonprobes is part of the input, then we call the graph a partitioned probe graph of . In this paper, we provide a recognition algorithm for partitioned probe permutation graphs with time complexity , where is the number of vertices of the input graph. We show that a probe permutation graph has at most minimal separators. As a consequence, for probe permutation graphs there exist polynomial-time algorithms solving problems like treewidth and minimum fill-in. We also characterize those graphs for which the probe graphs must be weakly chordal. [Copyright &y& Elsevier]

Abstract: A path cover of a graph is a set of pairwise vertex-disjoint paths such that the disjoint union of the vertices of these paths equals the vertex set of . The path cover problem is, given a graph, to find a path cover having the minimum number of paths. The path cover problem contains the Hamiltonian path problem as a special case since finding a path cover, consisting of a single path, corresponds directly to the Hamiltonian path problem. A graph is a distance-hereditary graph if each pair of vertices is equidistant in every connected induced subgraph containing them. The complexity of the path cover problem on distance-hereditary graphs has remained unknown. In this paper, we propose the first polynomial-time algorithm, which runs in O() time, to solve the path cover problem on distance-hereditary graphs. [Copyright &y& Elsevier]

Abstract: In this paper, we show that the clique-transversal number and the clique-independence number are equal for any distance-hereditary graph G. As a byproduct of proving that , we give a linear-time algorithm to find a minimum clique-transversal set and a maximum clique-independent set simultaneously for distance-hereditary graphs. [Copyright &y& Elsevier]

Abstract: A path cover of a graph is a family of vertex-disjoint paths that covers all vertices in V. Given a graph G, the path cover problem is to find a path cover of minimum cardinality. This paper presents a simple -time approximation algorithm for the path cover problem on circular-arc graphs given a set of n arcs with endpoints sorted. The cardinality of the path cover found by the approximation algorithm is at most one more than the optimal one. By using the result, we reduce the path cover problem on circular-arc graphs to the Hamiltonian cycle and Hamiltonian path problems on the same class of graphs in time. Hence the complexity of the path cover problem on circular-arc graphs is the same as those of the Hamiltonian cycle and Hamiltonian path problems on circular-arc graphs. [Copyright &y& Elsevier]

Abstract: A Hamiltonian path of a graph G is a simple path that contains each vertex of G exactly once. A Hamiltonian cycle of a graph is a simple cycle with the same property. The Hamiltonian path (resp. cycle) problem involves testing whether a Hamiltonian path (resp. cycle) exists in a graph. The 1HP (resp. 2HP) problem is to determine whether a graph has a Hamiltonian path starting from a specified vertex (resp. starting from a specified vertex and ending at the other specified vertex). The Hamiltonian problems include the Hamiltonian path, Hamiltonian cycle, 1HP, and 2HP problems. A graph is a distance-hereditary graph if each pair of vertices is equidistant in every connected induced subgraph containing them. In this paper, we present a unified approach to solving the Hamiltonian problems on distance-hereditary graphs in linear time. [Copyright &y& Elsevier]