We give the first polynomial-time algorithm that computes the bandwidth of bipartite permutation graphs. Bandwidth is an NP-complete graph layout problem that is notorious for its difficulty even on small graph classe...
详细信息
We give the first polynomial-time algorithm that computes the bandwidth of bipartite permutation graphs. Bandwidth is an NP-complete graph layout problem that is notorious for its difficulty even on small graph classes. For example, it remains NP-complete on caterpillars of hair length at most 3, a very restricted subclass of trees. Much attention has been given to designing approximation algorithms for computing the bandwidth, as it is NP-hard to approximate the bandwidth of general graphs with a constant factor guarantee. The problem is considered important even for approximation on restricted classes, with several distinguished results in this direction. Prior to our work, polynomial-time algorithms for exact computation of bandwidth were known only for caterpillars of hair length at most 2, chain graphs, cographs, and most interestingly, interval graphs. (C) 2008 Elsevier B.V. All rights reserved.
We consider the concepts of a t-total vertex cover and a t-total edge cover (t >= 1), which generalise the notions of a vertex cover and an edge cover, respectively. A t-total vertex (respectively edge) cover of a ...
详细信息
We consider the concepts of a t-total vertex cover and a t-total edge cover (t >= 1), which generalise the notions of a vertex cover and an edge cover, respectively. A t-total vertex (respectively edge) cover of a connected graph G is a vertex (edge) cover S of G such that each connected component of the subgraph of G induced by S has at least t vertices (edges). These definitions are motivated by combining the concepts of clustering and covering in graphs. Moreover they yield a spectrum of parameters that essentially range from a vertex cover to a connected vertex cover (in the vertex case) and from an edge cover to a spanning tree (in the edge case). For various values of t, we present NP-completeness and approximability results (both upper and lower bounds) and FPT algorithms for problems concerned with finding the minimum size of a t-total vertex cover, t-total edge cover and connected vertex cover, in particular improving on a previous FPT algorithm for the latter problem. (C) 2008 Elsevier B. V. All rights reserved.
A pure morphic sequence is a right-infinite, symbolic sequence obtained by iterating a letter-to-word substitution. For instance, the Fibonacci sequence and the Thue-Morse sequence, which play an important role in the...
详细信息
A pure morphic sequence is a right-infinite, symbolic sequence obtained by iterating a letter-to-word substitution. For instance, the Fibonacci sequence and the Thue-Morse sequence, which play an important role in theoretical computer science, are pure morphic. Define a coding as a letter-to-letter substitution. The image of a pure morphic sequence under a coding is called a morphic sequence. A sequence x is called uniformly recurrent if for each finite subword u of x there exists an integer l such that u occurs in every l-length subword of x. The paper mainly focuses on the problem of deciding whether a given morphic sequence is uniformly recurrent. Although the status of the problem remains open, we show some evidence for its decidability: in particular, we prove that it can be solved in polynomialtime on pure morphic sequences and on automatic sequences. In addition, we prove that the complexity of every uniformly recurrent, morphic sequence has at most linear growth: here, complexity is understood as the function that maps each positive integer n to the number of distinct n-length subwords occurring in the sequence.
This paper provides a fast computational algorithm for carrying out the performance analysis DEA technique, which reduces the computational requirements. The provided tests reduce the computational complexity when usi...
详细信息
This paper provides a fast computational algorithm for carrying out the performance analysis DEA technique, which reduces the computational requirements. The provided tests reduce the computational complexity when using the DEA technique to specify the efficiency position, the rank, and the returns-to-scale classification of DMUs under assessment.
Open Shortest Path First (OSPF) is the most commonly used intra-domain internet routing protocol. As the routes of paths are determined by basically only the link metrics, many paths may pass a link with small metric;...
详细信息
ISBN:
(纸本)9781424451654
Open Shortest Path First (OSPF) is the most commonly used intra-domain internet routing protocol. As the routes of paths are determined by basically only the link metrics, many paths may pass a link with small metric;therefore, there is high possibility that it causes the congestion of the link. It is essential that the number of the paths with large traffic in a link is limited to avoid a congestion;therefore, it is important to determine the link metrics so as to limit the number of the paths in a link. In this paper, we define this link metric decision problem, and we prove that it is NP-complete. In addition, when we restricted this problem to determine the metric of only a link, we show that it can be solved in polynomialtime.
We present a simple polynomial-time algorithm that recognises reflexive, symmetric graphs admitting a near-unanimity operation. Several other characterisations of these graphs are also presented. (c) 2004 Elsevier Inc...
详细信息
We present a simple polynomial-time algorithm that recognises reflexive, symmetric graphs admitting a near-unanimity operation. Several other characterisations of these graphs are also presented. (c) 2004 Elsevier Inc. All rights reserved.
George Dantzig created the simplex algorithm for linear programming, perhaps the most important algorithm developed in the 20th century. This paper traces a single historical thread: Dantzig's work on linear progr...
详细信息
George Dantzig created the simplex algorithm for linear programming, perhaps the most important algorithm developed in the 20th century. This paper traces a single historical thread: Dantzig's work on linear programming and its application and extension to combinatorial optimization, and the investigations it has stimulated about the performance of the simplex algorithm and the intrinsic complexity of linear programming and combinatorial optimization. (c) 2007 Elsevier B.V. All rights reserved.
In this paper, based on combined homotopy interior point method we propose an interior point algorithm for convex nonlinear programming. The algorithm ensures that the obtained iterative points are interior points of ...
详细信息
In this paper, based on combined homotopy interior point method we propose an interior point algorithm for convex nonlinear programming. The algorithm ensures that the obtained iterative points are interior points of the feasible set in terms of the technique of beta-cone neighborhood. We establish the global convergence of the algorithm. Furthermore, it is shown that the algorithm has O(root nL) iteration complexity. The preliminary numerical experiments indicate that the algorithm is efficient. (C) 2007 Elsevier Inc. All rights reserved.
Method of augmenting graphs is a general approach to solve the maximum independent set problem. As the problem is generally NP-hard, no polynomialtimealgorithms are available to implement the method. However, when r...
详细信息
Method of augmenting graphs is a general approach to solve the maximum independent set problem. As the problem is generally NP-hard, no polynomialtimealgorithms are available to implement the method. However, when restricted to particular classes of graphs, tile approach may lead to efficient solutions. A famous example of this type is the maximum matching algorithm: it finds a maximum matching in a graph G, which is equivalent to finding a maximum independent set in the line graph of G. In the particular case of line graphs, the method reduces to finding augmenting (alternating) chains. Recent investigations of more general classes of graphs revealed many more types of augmenting graphs. In the present paper we study the problem of finding augmenting graphs different from chains. To simplify this problem, we introduce tile notion of a redundant set. This allows us to reduce the problem to finding some basic augmenting graphs. As a result, we obtain a polynomialtime solution to the maximum independent set problem in a class of graphs which extends several previously studied classes including the line graphs. (c) 2008 Elsevier B.V. All rights reserved.
A new algorithm is presented for the D0L sequence equivalence problem which, when the alphabets are fixed, works in timepolynomial in the rest of the input data. The algorithm uses a polynomial encoding of words and ...
详细信息
A new algorithm is presented for the D0L sequence equivalence problem which, when the alphabets are fixed, works in timepolynomial in the rest of the input data. The algorithm uses a polynomial encoding of words and certain well-known properties of Z-rational sequences.
暂无评论