Given a graph G, the minimum edge ranking spanning tree problem (MERST) is to find a spanning tree of G whose edge ranking is minimum. However, this problem is known to be NP-hard for general graphs. In this paper, we...
详细信息
Given a graph G, the minimum edge ranking spanning tree problem (MERST) is to find a spanning tree of G whose edge ranking is minimum. However, this problem is known to be NP-hard for general graphs. In this paper, we show that the problem MERST has a polynomial time algorithm for split graphs, which have useful applications in practice. The result is also significant in the sense that this is a first non-trivial graph class for which the problem MERST is found to be polynomially solvable. We also show that the problem MERST for threshold graphs can be solved in linear time, where threshold graphs are known to be split. (c) 2006 Elsevier B.V. All rights reserved.
We show that the NP-complete FEEDBACK VERTEX SET problem, which asks for the smallest set of vertices to remove from a graph to destroy all cycles, is deterministically solvable in O(c(k) center dot m) time. Here, in ...
详细信息
We show that the NP-complete FEEDBACK VERTEX SET problem, which asks for the smallest set of vertices to remove from a graph to destroy all cycles, is deterministically solvable in O(c(k) center dot m) time. Here, in denotes the number of graph edges, k denotes the size of the feedback vertex set searched for, and c is a constant. We extend this to an algorithm enumerating all solutions in O(d(k) center dot m) time for a (larger) constant d. As a further result, we present a fixed-parameter algorithm with runtime O(2(k) center dot m(2)) for the NP-complete EDGE BIPARTIZATION problem, which asks for at most k edges to remove from a graph to make it bipartite. (C) 2006 Elsevier Inc. All rights reserved.
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.
In this paper, we propose a method which can be used to decompose a 2D or 3D constraint problem into a C-tree. With this decomposition, a geometric constraint problem can be reduced into basic merge patterns, which ar...
详细信息
In this paper, we propose a method which can be used to decompose a 2D or 3D constraint problem into a C-tree. With this decomposition, a geometric constraint problem can be reduced into basic merge patterns, which are the smallest problems we need to solve in order to solve the original problem in certain sense. Based on the C-tree decomposition algorithm, we implemented a software package MMP/Geometer. Experimental results show that MMP/Geometer finds the smallest decomposition for all the testing examples efficiently. (c) 2005 Elsevier Ltd. All rights reserved.
Locality behavior study is crucial for achieving good performance for irregular problems. graph algorithms with large, sparse inputs, for example, often times achieve only a tiny fraction of the potential peak perform...
详细信息
ISBN:
(纸本)9783540680390
Locality behavior study is crucial for achieving good performance for irregular problems. graph algorithms with large, sparse inputs, for example, often times achieve only a tiny fraction of the potential peak performance on current architectures. Compared with most numerical algorithms graph algorithms lay higher pressure on the memory system. In this paper, using the minimum spanning tree problem as an example, we study the locality behavior of graph algorithms, both sequential and parallel, for arbitrary, sparse instances. We show that the inherent locality of graph algorithms may not be favored by the current architecture, and parallel graph algorithms tend to have significantly poorer locality behaviors than their sequential counterparts. As memory hierarchy gets deeper and processors start to contain multi-cores, our study suggests that architectural support and new parallel algorithm designs are necessary for achieving good performance for irregular graph problems.
One of the fundamental problems encountered during the VLSI design flow is to find minimum length nets that connect specific nodes on the chip. The challenge lies in finding an efficient solution to the Steiner tree P...
详细信息
ISBN:
(纸本)9783901882197
One of the fundamental problems encountered during the VLSI design flow is to find minimum length nets that connect specific nodes on the chip. The challenge lies in finding an efficient solution to the Steiner tree Problem in graphs (SPG) that not only maximizes the routing efficiency but also lends itself well for fast implementation. In this paper, we propose a new and innovative approach for solving the Steiner tree problem, called the "Directed Convergence Heuristic (DCH)". In essence, the DCH based algorithm places entities called pawns on nodes that need to be connected. These pawns move towards each other in a directed fashion and while doing so, leave trails for constructing a Steiner tree between the nodes. When all the pawns converge at a node, the trails merge to create a Steiner tree. Experimental results on benchmark Steiner trees show that DCH is robust and converges faster while yielding competitive near optimal solutions. The algorithm is amenable for implementation on parallel computing architectures.
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...
详细信息
ISBN:
(纸本)9783540241324
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.
细胞自动机是一种离散动力系统。它包含了由细胞单元的状态构成的配制以及作用在配制上的传递规则。下面我们总是假设G=（V，E）是一个有限无向的简单连通图。图上的每一个顶点可以看作细胞自动机上的一个细胞单元，细胞单元上状态的值或者是0或者是1。如果每一个细胞单元的状态都被赋予了一个值，则所有细胞单元状态值的集合被称为细胞自动机上的一个配制。自动机的演化由局部传递规则决定。如果X是时刻t的一个配制，Y是局部传递规则作用在X后于时刻t+1的配制，那么Y称为X的后继，X被称为Y的前驱。在配制进化领域里的一个基本问题就是研究对于一个给定的目标配制确定它的前驱是否存在的问题。这个问题被称作前驱存在问题。更进一步，如果给定一个界β，寻找基数最多为β的前驱配制问题被称为界定前驱存在问题。给定一个有趣的目标配制1，即目标配制是每一个细胞单元的状态值都为1，我们将以基于局部规则σ+及σ下的图上的细胞自动机作为对象展开研究。
对于σ+规则，当初始配制为0，目标配制为1时，相应的前驱存在问题也被称为σ+全一问题或者直接称为全一问题[27]。Peled提出了一个等价的问题被称为点灯问题[22]。类似的，对于σ规则，当初始配制为0，目标配制为1时，相应的前驱存在问题被称为σ全一问题。为方便起见，目标配置的前驱也被称为解。
近年来全一问题已经被广泛的研究，见Sutner[29，31]，Barua和Ramakrishnan[2]以及Dodis和Winkler[11]。全一问题解的存在性问题已经被完全解决。用线形代数的方法，Sutner[28]证明了全一问题的解总是存在的，并给出了n×n的格子图上解的一些计数结果。Sutner曾提问是否可用图论的方法证明解的存在性问题[28]。Erikisson et al.[13]给出了解存在性的图论证明。进而，Chen et al.[6]给出了一个精巧的图论算法用来找到一般图上的解。如果我们也要求前驱配制中非零状态的细胞单元个数最少，相应的问题被简称为最小全一问题。这个问题已经被证明对于任意图是NP-完全问题[25]。最近，Broersma和Li又证明了对于二部图这个问题也是NP-完全的[3]。全一问题也可以被称为点点问
In this paper we consider the problem of determining a balanced ordering of the vertices of a graph;, that is, the neighbors of each vertex v are as evenly distributed to the left and right of v as possible. This prob...
详细信息
In this paper we consider the problem of determining a balanced ordering of the vertices of a graph;, that is, the neighbors of each vertex v are as evenly distributed to the left and right of v as possible. This problem, which has applications in graph drawing for example, is shown to be hard, and remains NP-hard for bipartite simple graphs with maximum degree six. We then describe and analyze a number of methods for determining a balanced vertex-ordering, obtaining optimal orderings for directed acyclic graphs, trees, and graphs with maximum degree three. For undirected graphs, we obtain a 13 / 8- approximation algorithm. Finally we consider the problem of determining a balanced vertex-ordering of a bipartite graph with a fixed ordering of one bipartition. When only the imbalances of the fixed vertices count, this problem is shown to be NP-hard. On the other hand, we describe an optimal linear time algorithm when the final imbalances of all vertices count. We obtain a linear time algorithm to compute an optimal vertex-ordering of a bipartite graph with one bipartition of constant size. (c) 2004, Elsevier B.V. All rights reserved.
暂无评论