Flow network simplification can reduce the size of the flow network and hence the amount of computation performed by flow algorithms. We present the first linear time algorithm for the undirected network case. We also...
详细信息
Flow network simplification can reduce the size of the flow network and hence the amount of computation performed by flow algorithms. We present the first linear time algorithm for the undirected network case. We also give an O(vertical bar E vertical bar * (vertical bar V vertical bar + vertical bar E vertical bar)) time algorithm for the directed case, an improvement over the previous best O(vertical bar V vertical bar + vertical bar E vertical bar(2) log vertical bar V vertical bar) time solution. Both of our algorithms are quite simple. (c) 2005 Elsevier B.V. All rights reserved.
Many questions regarding the Tower of Hanoi problem have been posed and answered during the years. Variants of the classical puzzle, such as allowing more than 3 pegs, and imposing limitations on the possible moves am...
详细信息
Many questions regarding the Tower of Hanoi problem have been posed and answered during the years. Variants of the classical puzzle, such as allowing more than 3 pegs, and imposing limitations on the possible moves among the pegs, raised the analogous questions for those variants. One such question is: given a variant, and a certain number of disks, find a pair of disk arrangements such that the minimal number of moves required for changing from the first to the second is maximal over all pairs. One of the main results of the paper is identifying these for the Cyclic(h) variants-the variants with h pegs arranged along a uni-directional circle-to be the pairs of perfect configurations where the destination peg is right before the source peg. (c) 2005 Elsevier B.V. All rights reserved.
The optimization problem of measuring all nodes in an electrical network by placing as few measurement units (PMUs) as possible is known as POWER DOMINATING SET. Nodes can be measured indirectly according to Kirchhoff...
详细信息
The optimization problem of measuring all nodes in an electrical network by placing as few measurement units (PMUs) as possible is known as POWER DOMINATING SET. Nodes can be measured indirectly according to Kirchhoff's law. We show that this problem can be solved in linear time for graphs of bounded treewidth and establish bounds on its parameterized complexity if the number of PMUs is the parameter. (c) 2006 Elsevier B.V. All rights reserved.
This paper gives a constructive proof that the register allocation problem for a uniform register set is solvable in polynomial time for SSA-form programs. (c) 2006 Elsevier B.V. All rights reserved.
This paper gives a constructive proof that the register allocation problem for a uniform register set is solvable in polynomial time for SSA-form programs. (c) 2006 Elsevier B.V. All rights reserved.
Asteroidal triple free (AT-free) graphs have been introduced as a generalization of interval graphs, since interval graphs are exactly the chordal AT-free graphs. While for interval graphs it is obvious that there is ...
详细信息
Asteroidal triple free (AT-free) graphs have been introduced as a generalization of interval graphs, since interval graphs are exactly the chordal AT-free graphs. While for interval graphs it is obvious that there is always a linear ordering of the vertices, such that for each triple of independent vertices the middle one intercepts any path between the remaining vertices of the triple, it is not clear that such an ordering exists for AT-free graphs in general. In this paper we study graphs that are defined by enforcing such an ordering. In particular, we introduce two subfamilies of AT-free graphs, namely, path orderable graphs and strong asteroid free graphs. Path orderable graphs are defined by a linear ordering of the vertices that is a natural generalization of the ordering that characterizes cocomparability graphs. On the other hand, motivation for the definition of strong asteroid free graphs comes from the fundamental work of Gallai on comparability graphs. We show that cocomparability graphs subset of path orderable graphs subset of strong asteroid free graphs subset of AT-free graphs. In addition, we settle the recognition question for the two new classes by proving that recognizing path orderable graphs is NP-complete, whereas the recognition problem for strong asteroid free graphs can be solved in polynomial time.
A k-tree is either a complete graph on k vertices or a graph G = (V, E) that contains a vertex whose neighbourhood in G induces a complete graph on k vertices and whose removal results in a k-tree. We present two new ...
详细信息
A k-tree is either a complete graph on k vertices or a graph G = (V, E) that contains a vertex whose neighbourhood in G induces a complete graph on k vertices and whose removal results in a k-tree. We present two new subclasses of k-trees and their properties. First, we present the definition and characterization of k-path graphs, based on the concept of k-paths, that generalizes the classic concept of paths. We also introduce the simple-clique k-trees, of which the maximal outerplanar graphs and the planar 3-trees are particular cases. Based on Characterization Theorems, we show recognition algorithms for both families. Finally, we establish the inclusion relations among these new classes and k-trees. (c) 2005 Elsevier B.V. All rights reserved.
Given an edge-capacitated undirected graph G = (V, E, C) with edge capacity c : E -> R+, n = vertical bar V vertical bar, an s - t edge cut C of G is a minimal subset of edges whose removal from G will separate s f...
详细信息
Given an edge-capacitated undirected graph G = (V, E, C) with edge capacity c : E -> R+, n = vertical bar V vertical bar, an s - t edge cut C of G is a minimal subset of edges whose removal from G will separate s from t in the resulting graph, and the capacity sum of the edges in C is the cut value of C. A minimum s - t edge cut is an s - t edge cut with the minimum cut value among all s - t edge cuts. A theorem given by Gomory and Hu states that there are only n - 1 distinct values among the n(n - 1)/2 minimum edge cuts in an edge-capacitated undirected graph G, and these distinct cuts can be compactly represented by a tree with the same node set as G, which is referred to the flow equivalent tree. In this paper we generalize their result to the node-edge cuts in a node-edge-capacitated undirected planar graph. We show that there is a flow equivalent tree for node-edge-capacitated undirected planar graphs, which represents the minimum node-edge cut for any pair of nodes in the graph through a novel transformation. (c) 2006 Elsevier B.V. All rights reserved.
We present an NC approximation algorithm for the weighted matching problem in graphs with an approximation ratio of (1- epsilon). This improves the previously best approximation ratio of (1/2 - epsilon) of an algorith...
详细信息
We present an NC approximation algorithm for the weighted matching problem in graphs with an approximation ratio of (1- epsilon). This improves the previously best approximation ratio of (1/2 - epsilon) of an algorithm for this problem. (c) 2006 Elsevier B.V. All rights reserved.
We study the problem of sharing in a fair manner the cost of a service provided to a set of players in the context of Cooperative Game Theory. We introduce a new fairness measure capturing the dissatisfaction (or happ...
详细信息
We study the problem of sharing in a fair manner the cost of a service provided to a set of players in the context of Cooperative Game Theory. We introduce a new fairness measure capturing the dissatisfaction (or happiness) of each player and we propose two cost sharing methods minimizing the maximum or average dissatisfaction of the clients for the classical minimum spanning tree game. (c) 2006 Elsevier B.V. All rights reserved.
We study the parsimony approach to haplotype inference, which calls for finding a set of haplotypes of minimum cardinality that explains an input set of genotypes. We prove that the problem is APX-hard even in very re...
详细信息
We study the parsimony approach to haplotype inference, which calls for finding a set of haplotypes of minimum cardinality that explains an input set of genotypes. We prove that the problem is APX-hard even in very restricted cases. On the positive side, we identify islands of tractability for the problem, by focusing on instances with specific structure of haplotype sharing among the input genotypes. We exploit the structure of those instance to give polynomial and constant-approximation algorithms to the problem. We also show that the general parsimony haplotyping problem is fixed parameter tractable.
暂无评论