The problem of enumerating the maximal cliques of a graph is a computationally expensive problem with applications in a number of different domains. Sometimes the benefit of knowing the maximal clique enumeration (MCE...
详细信息
The problem of enumerating the maximal cliques of a graph is a computationally expensive problem with applications in a number of different domains. Sometimes the benefit of knowing the maximal clique enumeration (MCE) of a single graph is worth investing the initial computation time. However, when graphs are abstractions of noisy or uncertain data, the MCE of several closely related graphs may need to be found, and the computational cost of doing so becomes prohibitively expensive. Here, we present a method by which the cost of enumerating the set of maximal cliques for related graphs can be reduced. By using the MCE for some baseline graph, the MCE for a modified, or perturbed, graph may be obtained by enumerating only the maximal cliques that are created or destroyed by the perturbation. When the baseline and perturbed graphs are relatively similar, the difference set between the two MCEs can be overshadowed by the maximal cliques common to both. Thus, by enumerating only the difference set between the baseline and perturbed graphs' MCEs, the computational cost of enumerating the maximal cliques of the perturbed graph can be reduced. We present necessary and sufficient conditions for enumerating difference sets when the perturbed graph is formed by several different types of perturbations. We also present results of an algorithm based on these conditions that demonstrate a speedup over traditional calculations of the MCE of perturbed, real biological networks. (C) 2010 Elsevier B.V. All rights reserved.
A graph is 2K(2)-partitionable if its vertex set can be partitioned into four nonempty parts A, B, C, D such that each vertex of A is adjacent to each vertex of B, and each vertex of C is adjacent to each vertex of D....
详细信息
A graph is 2K(2)-partitionable if its vertex set can be partitioned into four nonempty parts A, B, C, D such that each vertex of A is adjacent to each vertex of B, and each vertex of C is adjacent to each vertex of D. Determining whether an arbitrary graph is 2K(2)-partitionable is the only vertex-set partition problem into four nonempty parts according to external constraints whose computational complexity is open. We establish that the 2K(2)-partition problem parameterized by minimum degree is fixed-parameter tractable. We also show that for C-4-free graphs, circular-arc graphs, spiders, P-4-sparse graphs, and bipartite graphs the 2K(2)-partition problem can be solved in polynomial time. (C) 2009 Elsevier B.V. All rights reserved.
Multigrid solvers proved very efficient for solving massive systems of equations in various fields. These solvers are based on iterative relaxation schemes together with the approximation of the "smooth" err...
详细信息
Multigrid solvers proved very efficient for solving massive systems of equations in various fields. These solvers are based on iterative relaxation schemes together with the approximation of the "smooth" error function on a coarser level (grid). We present two efficient multilevel eigensolvers for solving massive eigenvalue problems that emerge in data analysis tasks. The first solver, a version of classical algebraic multigrid (AMG), is applied to eigenproblems arising in clustering, image segmentation, and dimensionality reduction, demonstrating an order of magnitude speedup compared to the popular Lanczos algorithm. The second solver is based on a new, much more accurate interpolation scheme. It enables calculating a large number of eigenvectors very inexpensively.
We classify into polynomial time or NP-complete all three nonempty part sandwich problems. This solves the polynomial dichotomy into polynomial time and NP-complete for this class of graph partition problems. (C) 2010...
详细信息
We classify into polynomial time or NP-complete all three nonempty part sandwich problems. This solves the polynomial dichotomy into polynomial time and NP-complete for this class of graph partition problems. (C) 2010 Elsevier B.V. All rights reserved.
Inspired by phylogenetic tree construction in computational biology, Lin et al. (The 11th Annual International Symposium on algorithms and Computation (ISAAC 2000), pp. 539-551, 2000) introduced the notion of a k -phy...
详细信息
Inspired by phylogenetic tree construction in computational biology, Lin et al. (The 11th Annual International Symposium on algorithms and Computation (ISAAC 2000), pp. 539-551, 2000) introduced the notion of a k -phylogenetic root. A k-phylogenetic root of a graph G is a tree T such that the leaves of T are the vertices of G, two vertices are adjacent in G precisely if they are within distance k in T, and all non-leaf vertices of T have degree at least three. The k-phylogenetic root problem is to decide whether such a tree T exists for a given graph G. In addition to introducing this problem, Lin et al. designed linear time constructive algorithms for ka parts per thousand currency sign4, while left the problem open for ka parts per thousand yen5. In this paper, we partially fill this hole by giving a linear time constructive algorithm to decide whether a given tree chordal graph has a 5-phylogenetic root;this is the largest class of graphs known to have such a construction.
We consider the problem of finding obnoxious centers in graphs. For arbitrary graphs with n vertices and m edges, we give a randomized algorithm with O(n log(2) n + m log n) expected time. For planar graphs, we give a...
详细信息
We consider the problem of finding obnoxious centers in graphs. For arbitrary graphs with n vertices and m edges, we give a randomized algorithm with O(n log(2) n + m log n) expected time. For planar graphs, we give algorithms with O(n log n) expected time and O(n log(3) n) worst-case time. For graphs with bounded treewidth, we give an algorithm taking O(n log n) worst-case time. The algorithms make use of parametric search and several results for computing distances on graphs of bounded treewidth and planar graphs.
We initiate the first systematic study of the NP-hard CLUSTER VERTEX DELETION (CVD) problem (unweighted and weighted) in terms of fixed-parameter algorithmics. In the unweighted case, one searches for a minimum number...
详细信息
We initiate the first systematic study of the NP-hard CLUSTER VERTEX DELETION (CVD) problem (unweighted and weighted) in terms of fixed-parameter algorithmics. In the unweighted case, one searches for a minimum number of vertex deletions to transform a graph into a collection of disjoint cliques. The parameter is the number of vertex deletions. We present efficient fixed-parameter algorithms for CVD applying the fairly new iterative compression technique. Moreover, we study the variant of CVD where the maximum number of cliques to be generated is pre-specified. Here, we exploit connections to fixed-parameter algorithms for (weighted) VERTEX COVER.
We present a polynomial-time approximation algorithm for legally coloring as many edges of a given simple graph as possible using two colors. It achieves an approximation ratio of roughly 0.842 and runs in 0(n(3)m) ti...
详细信息
We present a polynomial-time approximation algorithm for legally coloring as many edges of a given simple graph as possible using two colors. It achieves an approximation ratio of roughly 0.842 and runs in 0(n(3)m) time, where n (respectively, m) is the number of vertices (respectively, edges) in the input graph The previously best ratio achieved by a polynomial-time approximation algorithm was 5/6 approximate to 0 833 (C) 2010 Elsevier B.V. All rights reserved.
In this paper, we consider grammar-based compression for rooted ordered trees. For that purpose, we define an elementary ordered tree grammar (EOTG) by extending CFG, and then present a polynomial time algorithm which...
详细信息
In this paper, we consider grammar-based compression for rooted ordered trees. For that purpose, we define an elementary ordered tree grammar (EOTG) by extending CFG, and then present a polynomial time algorithm which approximates the smallest EOTG within a factor of O(n(5/6)). We also show that the grammar and algorithm can be modified for unordered trees of bounded degree. (C) 2010 Elsevier B.V. All rights reserved.
Permutation graphs form a well-studied subclass of cocomparability graphs. Permutation graphs are the cocomparability graphs whose complements are also cocomparability graphs. A triangulation of a graph G is a graph H...
详细信息
Permutation graphs form a well-studied subclass of cocomparability graphs. Permutation graphs are the cocomparability graphs whose complements are also cocomparability graphs. A triangulation of a graph G is a graph H that is obtained by adding edges to G to make it chordal. lino triangulation of G is a proper subgraph of H then H is called a minimal triangulation. The main theoretical result of the paper is a characterisation of the minimal triangulations of a permutation graph, that also leads to a succinct and linear-time computable representation of the set of minimal triangulations. We apply this representation to devise linear-time algorithms for various minimal triangulation problems on permutation graphs, in particular, we give linear-time algorithms for computing treewidth and minimum fill-in on permutation graphs. (C) 2010 Elsevier B.V. All rights reserved.
暂无评论