In a rooted triangulated planar graph, an outer vertex and two outer edges incident to it are designated as its root, respectively. Two plane embeddings of rooted triangulated planar graphs are defined to be equivalen...
详细信息
In a rooted triangulated planar graph, an outer vertex and two outer edges incident to it are designated as its root, respectively. Two plane embeddings of rooted triangulated planar graphs are defined to be equivalent if they admit an isomorphism such that the designated roots correspond to each other. Given a positive integer n, we give an O(n)-space and O(1)-time delay algorithm that generates all biconnected rooted triangulated planar graphs with at most n vertices without delivering two reflectively symmetric copies.
In most network analysis tools the computation of the shortest paths between all pairs of nodes is a fundamental step to the discovery of other properties. Among other properties is the computation of closeness centra...
详细信息
In most network analysis tools the computation of the shortest paths between all pairs of nodes is a fundamental step to the discovery of other properties. Among other properties is the computation of closeness centrality, a measure of the nodes that shows how central a vertex is on a given network. In this paper, the authors present a method to compute the All Pairs Shortest Paths on graphs that present two characteristics： abundance of nodes with degree value one, and existence of articulation points along the graph. These characteristics are present in many real life networks especially in networks that show a power law degree distribution as is the case of biological networks. The authors＇ method compacts the single nodes to their source, and then by using the network articulation points it disconnects the network and computes the shortest paths in the biconnected components. At the final step the authors proposed methods merges the results to provide the whole network shortest paths. The authors＇ method achieves remarkable speedup compared to state of the art methods to compute the shortest paths, as much as 7 fold speed up in artificial graphs and 3.25 fold speed up in real application graphs. The authors＇ performance improvement is unlike previous research as it does not involve elaborated setups since the authors algorithm can process significant instances on a popular workstation.
PrEd [Ber00] is a force-directed algorithm that improves the existing layout of a graph while preserving its edge crossing properties. The algorithm has a number of applications including: improving the layouts of pla...
详细信息
PrEd [Ber00] is a force-directed algorithm that improves the existing layout of a graph while preserving its edge crossing properties. The algorithm has a number of applications including: improving the layouts of planar graph drawing algorithms, interacting with a graph layout, and drawing Euler-like diagrams. The algorithm ensures that nodes do not cross edges during its execution. However, PrEd can be computationally expensive and overly-restrictive in terms of node movement. In this paper, we introduce ImPrEd: an improved version of PrEd that overcomes some of its limitations and widens its range of applicability. ImPrEd also adds features such as flexible or crossable edges, allowing for greater control over the output. Flexible edges, in particular, can improve the distribution of graph elements and the angular resolution of the input graph. They can also be used to generate Euler diagrams with smooth boundaries. As flexible edges increase data set size, we experience an execution/drawing quality trade off. However, when flexible edges are not used, ImPrEd proves to be consistently faster than PrEd.
The lower and the upper irredundance numbers of a graph G, denoted ir(G) and IR(G), respectively, are conceptually linked to the domination and independence numbers and have numerous relations to other graph parameter...
详细信息
The lower and the upper irredundance numbers of a graph G, denoted ir(G) and IR(G), respectively, are conceptually linked to the domination and independence numbers and have numerous relations to other graph parameters. It has been an open question whether determining these numbers for a graph G on n vertices admits exact algorithms running in time faster than the trivial Theta(2(n) center dot poly(n)) enumeration, also called the 2(n)-barrier. The main contributions of this article are exact exponential-time algorithms breaking the 2(n)-barrier for irredundance. We establish algorithms with running times of O*(1.99914(n)) for computing ir(G) and O*(1.9369(n)) for computing IR(G). Both algorithms use polynomial space. The first algorithm uses a parameterized approach to obtain (faster) exact algorithms. The second one is based, in addition, on a reduction to the Maximum Induced Matching problem providing a branch-and-reduce algorithm to solve it. (C) 2011 Elsevier B.V. All rights reserved.
The normal functioning of a living cell is characterized by complex interaction networks involving many different types of molecules. Associations detected between diseases and perturbations in well-defined pathways w...
详细信息
ISBN:
(纸本)9781450307963
The normal functioning of a living cell is characterized by complex interaction networks involving many different types of molecules. Associations detected between diseases and perturbations in well-defined pathways within such interaction networks have the potential to illuminate the molecular mechanisms underlying disease progression and response to treatment. In this paper, we present a computational method that compares expression profiles of genes in cancer samples to samples from normal tissues in order to detect perturbations of pre-defined pathways in the cancer. In contrast to many previous methods, our scoring function approach explicitly takes into account the interactions between the gene products in a pathway. Moreover, we compute the sub-pathway that has the highest score, as opposed to merely computing the score for the entire pathway. We use a permutation test to assess the statistical significance of the most perturbed sub-pathway. We apply our method to 20 pathways in the Netpath database and to the Global Cancer Map of gene expression in 18 cancers. We demonstrate that our method yields more sensitive results than alternatives that do not consider interactions or measure the perturbation of a pathway as a whole. We perform a sensitivity analysis to show that our approach is robust to modest changes in the input data. Our method confirms numerous well-known connections between pathways and cancers.
An outerplanar graph is a graph that can be embedded on the plane such that all the vertices lie on the exterior face and no two edges intersect except possibly at a common end-vertex. Five sequential algorithms had b...
详细信息
An outerplanar graph is a graph that can be embedded on the plane such that all the vertices lie on the exterior face and no two edges intersect except possibly at a common end-vertex. Five sequential algorithms had been proposed for rec ognizing outerplanar graph in the literature and all run in linear time and space. Although among them, the algorithms of Mitchell, Wiegers, and Tsin and Lin are obviously superior, no efforts had been made in comparing their performances during run-time. In this thesis, the aforementioned three algorithms are implemented and their performances are compared using a large number of randomly generated graphs. Furthermore, the algorithms of Mitchell and Wiegers are modified so that an out- erpalnar embedding is generated if the input graph is outerplanar. Correctness proofs of the modification are presented. It is also shown that the complexity of the modified algorithms remain linear in both time and space.
In recent years, many speed up techniques for DIJKSTRA Algorithm have been developed. Unfortunately, research mainly focused on road networks although fast algorithms are also needed for other applications like timeta...
详细信息
In recent years, many speed up techniques for DIJKSTRA Algorithm have been developed. Unfortunately, research mainly focused on road networks although fast algorithms are also needed for other applications like timetable information systems. Even worse, the adaption of recently developed techniques to graphs deriving from timetable information problems is often more complicated than expected. In this work, we check whether results from road networks are transferable to timetable information systems. To this end, we present an extensive experimental study of the most prominent speed up techniques on inputs deriving from different applications. It turns out that recently developed techniques are much slower on graphs derived from timetable information problems than on road networks. In addition, we gain interesting insights into the behavior of speed up techniques in general. (C) 2010 Wiley Periodicals, Inc. NETWORKS, Vol. 57(1), 38-52 2011
Modeling by constraints enables users to describe shapes by specifying relationships between geometric elements. These relationships are called constraints. A constraint solver derives then automatically the design in...
详细信息
Modeling by constraints enables users to describe shapes by specifying relationships between geometric elements. These relationships are called constraints. A constraint solver derives then automatically the design intended by exploiting these constraints. The constraints solvers can be classified in four categories: symbolic, numerical, rule-oriented and graph-constructive solvers. The graph constructive approach is widely used in recent Computer Aided Design (CAD) systems. in this paper, we present a decomposition-recombination (DR) planning algorithm, called S-DR, that uses a graph reduction method to solve systems of 2D geometric constraints. Based on the key concept of skeletons, S-DR planner figures out a plan for decomposing a well constrained system into small sub-systems and recombines the solutions of these sub-systems to derive the solution of the entire system. (C) 2010 Elsevier Ltd. All rights reserved.
The square H-2 of a graph H is obtained from H by adding new edges between every two vertices having distance two in H. A block graph is one in which every block is a clique. For the first time, good characterizations...
详细信息
The square H-2 of a graph H is obtained from H by adding new edges between every two vertices having distance two in H. A block graph is one in which every block is a clique. For the first time, good characterizations and a linear time recognition of squares of block graphs are given in this paper. Our results generalize several previous known results on squares of trees. (C) 2009 Elsevier B.V. All rights reserved.
We present an output sensitive algorithm for computing a maximum independent set of an unweighted circle graph. Our algorithm requires O(n min{d,alpha}) time at worst, for an n vertex circle graph where a is the indep...
详细信息
We present an output sensitive algorithm for computing a maximum independent set of an unweighted circle graph. Our algorithm requires O(n min{d,alpha}) time at worst, for an n vertex circle graph where a is the independence number of the circle graph and d is its density. Previous algorithms for this problem required Theta(nd) time at worst. (C) 2010 Elsevier B.V. All rights reserved.
暂无评论