The class of fork-free graphs is an extension of claw-free graphs and their subclass of line graphs. The first polynomial-time solution to the maximum weight independent set problem in the class of line graphs, which ...
详细信息
ISBN:
(纸本)9780898716054
The class of fork-free graphs is an extension of claw-free graphs and their subclass of line graphs. The first polynomial-time solution to the maximum weight independent set problem in the class of line graphs, which is equivalent to the maximum matching problem in general graphs, has been proposed by Edmonds in 1965 and then extended to the entire class of claw-free graphs by Minty in 1980. Recently, Alekseev proposed a solution for the larger class of fork-free graphs, but only for the unweighted version of the problem, i.e. finding an independent set of maximum cardinality. In the present paper, we describe the first polynomial-time algorithm to solve the problem for weighted fork-free graphs.
The class of fork-free graphs is an extension of claw-free graphs and their subclass of line graphs. The first polynomial-time solution to the maximum weight independent set problem in the class of line graphs, which ...
详细信息
ISBN:
(纸本)9780898716054
The class of fork-free graphs is an extension of claw-free graphs and their subclass of line graphs. The first polynomial-time solution to the maximum weight independent set problem in the class of line graphs, which is equivalent to the maximum matching problem in general graphs, has been proposed by Edmonds in 1965 and then extended to the entire class of claw-free graphs by Minty in 1980. Recently, Alekseev proposed a solution for the larger class of fork-free graphs, but only for the unweighted version of the problem, i.e. finding an independent set of maximum cardinality. In the present paper, we describe the first polynomial-time algorithm to solve the problem for weighted fork-free graphs.
This paper deals with an interesting problem about how to efficiently compute the number of different efficient paths between an origin-destination pair for a transportation network because these efficient paths are t...
详细信息
This paper deals with an interesting problem about how to efficiently compute the number of different efficient paths between an origin-destination pair for a transportation network because these efficient paths are the possible paths used by drivers to some extent. Based on a novel triangle operation derived, it first presents a polynomial-time combinatorial algorithm that can obtain the number of different simple paths between any two nodes for an acyclic network as well as the total travel cost of these paths. This paper proceeds to develop a combinatorial algorithm with polynomial-time complexity for both counting the different efficient paths between an origin-destination pair and calculating the total travel cost of these paths. As for applications, this paper shows that the preceding two algorithms can yield the lower and upper bounds for the number of different simple paths between an origin-destination pair, while it has already be recognized that a polynomial-time algorithm getting such a number does not exist for a general network. Furthermore, the latter algorithm can be applied for developing a heuristic method for the traffic counting location problem arising from the origin-destination matrix estimation problems.
This paper deals with minimum spanning tree problems where each edge weight is a fuzzy random variable. In order to consider the imprecise nature of the decision maker's judgment, a fuzzy goal for the objective fu...
详细信息
This paper deals with minimum spanning tree problems where each edge weight is a fuzzy random variable. In order to consider the imprecise nature of the decision maker's judgment, a fuzzy goal for the objective function is introduced. A novel decision making model is constructed based on possibility theory and on a stochastic programming model. It is shown that the problem including both randomness and fuzziness is reduced to a deterministic equivalent problem. Finally, a polynomial-time algorithm is provided to solve the problem.
In this paper, we introduce the 1 - K robotic-cell scheduling problem, whose solution can be reduced to solving a TSP on specially structured permuted Monge matrices, we call b-decomposable matrices. We also review a ...
详细信息
In this paper, we introduce the 1 - K robotic-cell scheduling problem, whose solution can be reduced to solving a TSP on specially structured permuted Monge matrices, we call b-decomposable matrices. We also review a number of other scheduling problems which all reduce to solving TSP-s on permuted Monge matrices. We present the important insight that the TSP on b-decomposable matrices can be solved in polynomialtime by a special adaptation of the well-known subtour-patching technique. We discuss efficient implementations of this algorithm on newly defined subclasses of permuted Monge matrices.
The class of 2K(2)-free graphs includes several interesting subclasses such as split, pseudo-split, threshold graphs, complements to chordal, interval or trivially perfect graphs. The fundamental property of 2K(2)-fre...
详细信息
The class of 2K(2)-free graphs includes several interesting subclasses such as split, pseudo-split, threshold graphs, complements to chordal, interval or trivially perfect graphs. The fundamental property of 2K(2)-free graphs is that they contain polynomially many maximal independent sets. As a consequence, several important problems that are NP-hard in general graphs, such as 3-colorability, maximum weight independent set (WIS), minimum weight independent dominating set (WID), become polynomial-time solvable when restricted to the class of 2K(2)-free graphs. In the present paper, we extend 2K(2)-free graphs to larger classes with polynomial-time solvable WIS or WID. In particular, we show that WIS can be solved in polynomialtime for (K-2 + K-1,K-3)-free graphs and WID for (K-2 + K-1.2)-free graphs. The latter result is in contrast with the fact that independent domination is NP-hard in the class of 2K(1.2)-free graphs, which has been recently proven by Zverovich. (C) 2004 Elsevier B.V. All rights reserved.
The recognition of 3-colorable graphs is an NP-complete problem, while 2-colorable (i.e., bipartite) graphs can be recognized in polynomialtime. To make the complexity gap more precise, we study intermediate graph cl...
详细信息
The recognition of 3-colorable graphs is an NP-complete problem, while 2-colorable (i.e., bipartite) graphs can be recognized in polynomialtime. To make the complexity gap more precise, we study intermediate graph classes and respective problems. This note proposes a conjecture that separates difficult instances of the problem from polynomially solvable ones and proves the "polynomial" part of the conjecture. (c) 2005 Elsevier B.V. All rights reserved.
We study the scheduling of m-machine reentrant robotic cells, in which parts need to reenter machines several times before they are finished. The problem is to find the sequence of 1-unit robot move cycles and the par...
详细信息
We study the scheduling of m-machine reentrant robotic cells, in which parts need to reenter machines several times before they are finished. The problem is to find the sequence of 1-unit robot move cycles and the part processing sequence which jointly minimize the cycle time or the makespan. When m = 2, we show that both the cycle time and the makespan minimization problems are polynomially solvable. When m = 3, we examine a special class of reentrant robotic cells with the cycle time objective. We show that in a three-machine loop-reentrant robotic cell, the part sequencing problem under three out of the four possible robot move cycles for producing one unit is strongly NP-hard. The part sequencing problem under the remaining robot move cycle can be solved easily. Finally, we prove that the general problem, without restriction to any robot move cycle, is also intractable.
作者：
Faragó, AUniv Texas
Erik Jonsson Sch Engn & Comp Sci Dept Comp Sci Richardson TX 75083 USA
In a number of applications we want to find a densest subgraph in an input graph. The complexity of this task depends on how density is defined. If density means the ratio of the number of edges and the number of vert...
详细信息
ISBN:
(纸本)1932415718
In a number of applications we want to find a densest subgraph in an input graph. The complexity of this task depends on how density is defined. If density means the ratio of the number of edges and the number of vertices in the subgraph, then the algorithmic problem has long been known efficiently solvable. On the other hand, the task becomes NP-hard with closely related but somewhat modified concepts of density. To capture many different densiry concepts of interest in a common model, we define a general concept of density, called G-density. Looking for a subgraph with maximum TG-density means that we search for a subgraph G' in the input graph, such that G' has the highest number of G-type subgraphs relative to the number of vertices in G'. Here G is an arbitrary class of graphs, which determines which subgraphs are counted in computing the density This concept subsumes many natural and important particular density concepts. Our main result is that for any fixed class G, a subgraph of maximum G-density can be found in polynomialtime in any input graph.
The paper considers the flow shop scheduling problems to minimize the makespan, provided that an individual precedence relation is specified on each machine. A fairly complete complexity classification of problems wit...
详细信息
The paper considers the flow shop scheduling problems to minimize the makespan, provided that an individual precedence relation is specified on each machine. A fairly complete complexity classification of problems with two and three machines is obtained.
暂无评论