34486647
Minimum Fill-In on Circle and Circular-Arc Graphs
We present two algorithms solving the minimum fill-in problem on circle graphs and on circular-arc graphs in time O(n3).
38611039
Vertex Ranking of Asteroidal Triple-Free Graphs
We present an efficient algorithm for computing the vertex ranking number of an asteroidal triple-free graph. Its running time is bounded by a polynomial in the number of vertices and the number of minimal separators of the input graph.
43443657
A note on visibility graphs
Abstract Given a set S = {s1, s2,…, sn} of vertical line segments, s1, sj see each other if there is a horizontal line segment which intersects them, but does not intersect any other line segment between them. A visibility graph G of vertices {v1, v2,…, vn} is put into a one-to-one correspondence with S, such that si corresponds to v1, and edge {vi, vj} exists in G iff si, sj see each other. We prove that any visibility graph G is ipo-triangular, that is, it can be transformed into a planar multigraph with all triangular finite faces, by successive duplications of existing edges of G. Conversely we prove that any ipo-triangular graph is a visibility graph for some set S.
195859283
On fixed edges and edge-reconstruction of series-parallel networks
A graph configuration is a vertex labeled simple graph. We say a configuration is exclusive for graphs with a property in a class of graphs if every graph in the class containing the configuration has the property. We use the method of exclusive configurations to search for graphs without fixed edges and forced edges investigate the fixed edges. An edge e of a graph G is said to be a fixed edge if G-e+e'/spl cong/G implies that e'=e, and a forced edge if G-e+e' is an edge-reconstruction of G implies that e'=e. It is proved that all series-parallel networks contain fixed edges and forced edge except P/sub 2//spl times/K/sub 1/ and P/sub 3//spl times/K/sub 1/. A similar method is used to investigate the alternative wire problem in circuit design. Let G be a Boolean network and w a wire in G. Wire w' is said to be an alternative wire of w if w'/spl ne/w and G-w+w' has the same functionality as that of G. A wire is said to be fixed if it has no alternative wire. We present a set of exclusive configurations for Boolean networks in which every wire is fixed.
46500499
Minimum Fill-in on Circle and Circular-Arc Graphs
We present two algorithms solving the minimum fill-in problem on circle graphs and on circular-arc graphs in timeO(n3).
15615911
Time-varying shortest path problems with constraints
The shortest path problem is considered with yet another extension. The transit times b(x,y,u) and the arc costs c(x,y,u) on arc (x,y) vary as a function of the departure time u at the beginning vertex of the arc. The problem considered is to find the shortest path between a pair of nodes such that the total traverse time is lesser than some specified value T. Waiting times at nodes are considered as decision variables in this paper as well. Three variations of the problem are analyzed in which the waiting times are allowed to be arbitrary, the waiting times are zero and the waiting time has an upper bound at each vertex. Algorithms are also discussed to solve the problem. Some of the applications of the problem are encountered in communication networks and freight delivery problems. Suppose that some freight is to be sent from one city to another in a network before a deadline T. Different types of freight services with different costs and transit times are available between the two cities. An optimal solution would have to specify the route as well as the waiting times of the freight at each city so that the overall cost is minimum. A dynamic programming approach is used to compute the shortest path from the origin node to the destination node. Three cases are considered for the waiting times and an algorithm is suggested for each of those cases. This problem is obviously an NP-Complete problem as it is more difficult to solve than a problem with constant transit times and arc costs such as the previous problem which is NP-Complete. Some definitions: Waiting time w(x i) at a vertex x i is a nonnegative integer with an upper bound U x >= 0. Let P be a path from vertex x 1 to x r. The departure time T(x i) at a vertex x i can be expressed as below: T(x 1) = w(x 1) The departure time for all other vertices on the path can be expressed recursively as : The time of path P is defined as T(x r) where x r is the final node on the path..
37608950
Efficient Heuristics for Orientation Metric and Euclidean Steiner Tree Problems
AbstractWe consider Steiner minimum trees (SMT) in the plane, where only orientations with angle
$${\sigma }$$
 , 0 ≤ i ≤ σ − 1 and σ an integer, are allowed. The orientations define a metric, called the orientation metric, λσ, in a natural way. In particular, λ2 metric is the rectilinear metric and the Euclidean metric can beregarded as λ∞ metric. In this paper, we provide a method to find an optimal λσ SMT for 3 or 4 points by analyzing the topology of λσ SMT's in great details. Utilizing these results and based on the idea of loop detection first proposed in Chao and Hsu, IEEE Trans. CAD, vol. 13, no. 3, pp. 303–309, 1994, we further develop an O(n2) time heuristic for the general λσ SMT problem, including the Euclidean metric. Experiments performed on publicly available benchmark data for 12 different metrics, plus the Euclidean metric, demonstrate the efficiency of our algorithms and the quality of our results.
8508688
New algorithms for the rectilinear Steiner tree problem
An approach to constructing the rectilinear Steiner tree (RST) of a given set of points in the plane, starting from a minimum spanning tree (MST), is discussed. The main idea in this approach is to find layouts for the edges of the MST that maximize the overlaps between the layouts, thus minimizing the cost (i.e. wire length) of the resulting rectilinear Steiner tree. Two algorithms for constructing rectilinear Steiner trees from MSTs, which are optimal under the conditions that the layout of each edge of the MST is an L shape or any staircase, respectively, are described. The first algorithm has linear time complexity and the second algorithm has a higher polynomial time complexity. Steiner trees produced by the second algorithm have a property called stability, which allows the rerouting of any segment of the tree, while maintaining the cost of the tree, and without causing overlaps with the rest of the tree. Stability is a desirable property in VLSI global routing applications. >
7582792
Relative contributions of desolvation, inter- and intramolecular interactions to binding affinity in protein kinase systems
In several previous studies, we performed sensitivity analysis to gauge the relative importance of different atomic partial charges in determining protein-ligand binding. In this work, we gain further insights by decomposing these results into three contributions: desolvation, intramolecular interactions, and intermolecular interactions, again based on a Poisson continuum electrostatics model. Three protein kinase-inhibitor systems have been analyzed: CDK2-deschloroflavopiridol, PKA-PKI, and LCK-PP2. Although our results point out the importance of specific intermolecular interactions to the binding affinity, they also reveal the remarkable contributions from the solvent-mediated intramolecular interactions in some cases. Thus, it is necessary to look beyond analyzing protein-ligand interactions to understand protein-ligand recognition or to gain insights into designing ligands and proteins. In analyzing the contributions of the three components to the overall binding free energy, the PKA-PKI system with a much larger ligand was found to behave differently from the other two systems with smaller ligands. In the former case, the intermolecular interactions are very favorable, and together with the favorable solvent-mediated intramolecular interactions, they overcome the large desolvation penalties to give a favorable electrostatics contribution to the overall binding affinity. On the other hand, the other two systems with smaller ligands only present modest intermolecular interactions and they are not or are only barely sufficient to overcome the desolvation penalty even with the aid of the favorable intramolecular contributions. As a result, the binding affinity of these two systems do not or only barely benefit from electrostatics contributions.
29097074
Analysis on the Session Life Time Distribution of Gnutella
1566543
Minimizing Mean Flow Time with Error Constraint
Abstract. We consider the problem of minimizing mean flow time for the Imprecise Computation Model introduced by Lin et al. A task system TS=({Ti},{r(Ti)},{d(Ti)},{m(Ti)},{o(Ti)})  consists of a set of n  independent tasks, where r(Ti),d(Ti),m(Ti) , and o(Ti)  denote the ready time, deadline, execution time of the mandatory part, and execution time of the optional part of Ti , respectively. Given a task system TS  and an error threshold K , our goal is to find a preemptive schedule on one processor such that the average error is no more than K  and the mean flow time of the schedule is minimized. Such a schedule is called an optimal schedule. In this article we show that the problem of finding an optimal schedule is NP-hard, even if all tasks have identical ready times and deadlines. A pseudopolynomial-time algorithm is given for a set of tasks with identical ready times and deadlines, and oppositely ordered mandatory execution times and total execution times (i.e., there is a labeling of tasks such that m(Ti)≤ m(Ti+1)  and m(Ti)+o(Ti)≥ m(Ti+1)+o(Ti+1)  for each 1≤ i<n  ). Finally, polynomial-time algorithms are given for (1) a set of tasks with identical ready times, and similarly ordered mandatory execution times and total execution times and (2) a set of tasks with similarly ordered ready times, deadlines, mandatory execution times, and total execution times.