Given a directed graph G and a pair of nodes s and t, an s-t bridge of G is an edge whose removal breaks all s-t paths of G (and thus appears in all s-t paths). Computing all s-t bridges of G is a basic graph problem,...
详细信息
Given a directed graph G and a pair of nodes s and t, an s-t bridge of G is an edge whose removal breaks all s-t paths of G (and thus appears in all s-t paths). Computing all s-t bridges of G is a basic graph problem, solvable in linear time. In this paper, we consider a natural generalisation of this problem, with the notion of "safety" from bioinformatics. We say that a walk W is safe with respect to a set W of s-t walks, if W is a subwalk of all walks in W. We start by considering the maximal safe walks when W consists of: all s-t paths, all s-t trails, or all s-t walks of G. We show that the solutions for the first two problems immediately follow from finding all s-t bridges after incorporating simple characterisations. However, solving the third problem requires non-trivial techniques for incorporating its characterisation. In particular, we show that there exists a compact representation computable in linear time, that allows outputting all maximal safe walks in time linear in their length. Our solutions also directly extend to multigraphs, except for the second problem, which requires a more involved approach. We further generalise these problems, by assuming that safety is defined only with respect to a subset of visible edges. Here we prove a dichotomy between the s-t paths and s-t trails cases, and the s-t walks case: the former two are NP-hard, while the latter is solvable with the same complexity as when all edges are visible. We also show that the same complexity results hold for the analogous generalisations of s-t articulation points (nodes appearing in all s-t paths). We thus obtain the best possible results for natural "safety"-generalisations of these two fundamental graph problems. Moreover, our algorithms are simple and do not employ any complex data structures, making them ideal for use in practice.
The Phylogenetic kth Root Problem (PRk) is the problem of finding a (phylogenetic) tree T from a given graph G = (V, E) such that (1) T has no degree-2 internal nodes, (2) the external nodes (i.e., leaves) of T are ex...
详细信息
The Phylogenetic kth Root Problem (PRk) is the problem of finding a (phylogenetic) tree T from a given graph G = (V, E) such that (1) T has no degree-2 internal nodes, (2) the external nodes (i.e., leaves) of T are exactly the elements of V, and (3) (u, v) is an element of E if and only if the distance between it and v in tree T is at most k, where k is some fixed threshold k. Such a tree T, if exists. is called a phylogenetic kth root of graph G. The computational complexity of PRk is open, except for k <= 4. Recently, Chen et al. investigated PRk under a natural restriction that the maximum degree of the phylogenetic root is bounded from above by a constant. They presented a linear-time algorithm that determines if a given connected G has such a phylogenetic kth root, and if so. demonstrates one. In this paper, we supplement their work by presenting a linear-time algorithm for disconnected graphs. (c) 2005 Elsevier Inc. All rights reserved.
Collaborative and competitive applications require that participants receive messages almost simultaneously and before a specified time. These requirements have been addressed by the delay variation-bounded multicasti...
详细信息
Collaborative and competitive applications require that participants receive messages almost simultaneously and before a specified time. These requirements have been addressed by the delay variation-bounded multicasting tree (DVBMT) problem. In this paper, we propose the interval multicast subgraph (IMS) problem to address these requirements. IMS addresses these constraints with an interval of acceptable delay values for paths as user input from a source to a destination, eliminating the need to optimize delays for a variation value. By solving IMS rather than DVBMT and other variants of DVBMT, we are able to find solutions for larger graphs more efficiently. Our proposed interval multicast algorithm (IMA) accounts for an interval of acceptable delay as user input and guarantees the weight of each path from the source to a distinct destination is within the given interval if that path exists. We provide proofs of correctness and complexity of IMA, as well as simulation experiments, to illustrate the effects of various parameters on our algorithm. Simulations show that IMS is significantly less costly than finding the minimum variation for the average and best case. By remodeling the DVBMT problem to IMS, we have created a new problem that addresses the quality of service requirements of multicasting and is able to be solved efficiently for the average case for relatively large graphs.
This paper presents an efficient algorithm to generate all (unordered) rooted trees with exactly vertices including exactly k leaves. There are known results on efficient enumerations of some classes of graphs embedde...
详细信息
This paper presents an efficient algorithm to generate all (unordered) rooted trees with exactly vertices including exactly k leaves. There are known results on efficient enumerations of some classes of graphs embedded on a plane, for instance, biconnected and triconnected triangulations [3], [6], and floorplans [4]. On the other hand, it is difficult to enumerate a class of graphs without a fixed embedding. The paper is on enumeration of rooted trees without a fixed embedding. We already proposed an algorithm to generate all "ordered" trees with 17 vertices including k leaves [11], while the algorithm cannot seem to efficiently generate all (unordered) rooted trees with it vertices including k leaves. We design a simple tree structure among such trees, then by traversing the tree structure we generate all such trees in constant time per tree in the worst case. By repeatedly applying the algorithm for each k = 1, 2, . . . , n - 1, we can also generate all rooted trees with exactly n vertices.
As graphs grow in size, many real-world graphs are difficult to load into the primary memory of a computer. Thus, computing depth-first search (DFS) results (i.e., depth-first order or DFS-Tree) on the semi-external m...
详细信息
As graphs grow in size, many real-world graphs are difficult to load into the primary memory of a computer. Thus, computing depth-first search (DFS) results (i.e., depth-first order or DFS-Tree) on the semi-external memory model is important to investigate. Semi external algorithms assume that the primary memory can at least hold a spanning tree T of a graph G and gradually restructure T into a DFS-Tree, which is nontrivial. In this paper, we present a comprehensive study for the semi-external DFS problem. Based on a theoretical analysis of this problem, we introduce a new semi-external DFS algorithm called EPDFS with a lightweight index N thorn -index. Unlike traditional algorithms, we focus on addressing such a complex problem efficiently with fewer I/Os, simpler CPU calculations (implementation-friendly), and less random I/O accesses (key-to-efficiency). Extensive experimental evaluations are performed on both synthetic and real graphs, and experimental results confirm that the proposed EP-DFS algorithm markedly outperforms existing algorithms. (c) 2022 Elsevier Inc. All rights reserved.
For a graph G = (V, E) with no isolated vertices, a set D subset of V is called a semipaired dominating set of G if (i) D is a dominating set of G, and (ii) D can be partitioned into two element subsets such that the ...
详细信息
For a graph G = (V, E) with no isolated vertices, a set D subset of V is called a semipaired dominating set of G if (i) D is a dominating set of G, and (ii) D can be partitioned into two element subsets such that the vertices in each two element set are at distance at most two. The minimum cardinality of a semipaired dominating set of G is called the semipaired domination number of G, and is denoted by gamma(pr2)(G). TheMINIMUM SEMIPAIRED DOMINATION problem is to find a semipaired dominating set of G of cardinality gamma(pr2)(G). In this paper, we initiate the algorithmic study of the MINIMUM SEMIPAIRED DOMINATION problem. We show that the decision version of the MINIMUM SEMIPAIRED DOMINATION problem is NP-complete for bipartite graphs and chordal graphs. On the positive side, we present a linear-time algorithm to compute a minimum cardinality semipaired dominating set of interval graphs. We also propose a 1 + ln(2 Delta + 2)-approximation algorithm for the MINIMUM SEMIPAIRED DOMINATION problem, where Delta denotes the maximum degree of the graph and show that the MINIMUM SEMIPAIRED DOMINATION problem cannot be approximated within (1 - epsilon) ln vertical bar V vertical bar for any epsilon > 0 unless P=NP.
The linear-width of a graph G is defined to be the smallest integer k such that the edges of G can be arranged in a linear ordering (e(1),...,e(r)) in such a way that for every i = 1,..., r - 1, there are at most k ve...
详细信息
The linear-width of a graph G is defined to be the smallest integer k such that the edges of G can be arranged in a linear ordering (e(1),...,e(r)) in such a way that for every i = 1,..., r - 1, there are at most k vertices incident to edges that belong both to {e(1),...,e(i)} and to {e(i+1),...,e(r)}. In this paper, we give a set of 57 graphs and prove that it is the set of the minimal forbidden miners for the class of graphs with linear-width at most two. Our proof also gives a linear time algorithm that either reports that a given graph has linear-width more than two or outputs an edge ordering of minimum linear-width. We further prove a structural connection between linear-width and the mixed search number which enables us to determine, for any k greater than or equal to 1, the set of acyclic forbidden miners for the class of graphs with linear-width less than or equal to k. Moreover, due to this connection, our algorithm can be transfered to two linear time algorithms that check whether a graph has mixed search or edge search number at most two and, if so, construct the corresponding sequences of search moves. (C) 2000 Elsevier Science B.V. All rights reserved.
The community structure is one of the most important patterns in network. Since finding the communities in the network can significantly improve our understanding of the complex relations, lots of work has been done i...
详细信息
The community structure is one of the most important patterns in network. Since finding the communities in the network can significantly improve our understanding of the complex relations, lots of work has been done in recent years. Yet it still lies vacant on the exact definition and practical algorithms for community detection. This paper proposes a novel definition for community which overcomes the drawbacks of existing methods. With the new definition, efficient community detection algorithms are developed, which take advantage of additive topological and other constrains to discover communities in arbitrary shape based on the feedback. The algorithm has a linear run time with the size of graph. Experimental results demonstrate that the community definition in this paper is effective and the algorithm is scalable for large graphs. (C) 2013 Elsevier B.V. All rights reserved.
Incremental graph algorithms deal with recomputing properties of a graph after an incremental change is made to that graph, such as adding and deleting vertices and edges. Such recomputations are ''updating...
详细信息
Incremental graph algorithms deal with recomputing properties of a graph after an incremental change is made to that graph, such as adding and deleting vertices and edges. Such recomputations are ''updating'' graph properties. Efficient parallel algorithms are presented for edge and vertex insertion updating in a minimum spanning tree (MST) due to changes in edge costs or in vertex insertion, when a new node is inserted in the underlying graph. The algorithms are derived from a computational model of an unbounded parallel random access machine where simultaneous reads, but not simultaneous writes, are allowed into the same memory location. They are shown to be more efficient than previously proposed algorithms for the MST updating problem, requiring only O(log n) time and certain processors. Main features of the algorithms are that they: 1. solve MST updating problems based on the use of an inverted tree, and 2. exploit a certain MST property that allows novel solution for vertex updating.
In this brief, we study first- and second-order consensus algorithms for the scale-free small-world Koch network, where vertices are subject to white noise. We focus on three cases of consensus schemes: 1) first-order...
详细信息
In this brief, we study first- and second-order consensus algorithms for the scale-free small-world Koch network, where vertices are subject to white noise. We focus on three cases of consensus schemes: 1) first-order leaderless algorithm;2) first-order algorithm with a single leader;and 3) second-order leaderless algorithm. We are concerned with the coherence of the Koch network in the H-2 norm, which captures the level of agreement of vertices in face of stochastic disturbances. Based on the particular network construction, we derive explicit expressions of the coherence for all the three consensus algorithms, as well as their dependence on the network size. Particularly, for the first-order leader-follower model, we show that coherence relies on the shortest-path distance between the leader and the largest-degree vertices, as well as the degree of the leader. The asymptotic behaviors for coherence of the three consensus algorithms in Koch network behave differently from those associated with other networks lacking scale-free small-world features, indicating significant influences of the scale-free small-world topology on the performance of the consensus algorithms in noisy environments.
暂无评论