Polarity and monopolarity are properties of graphs defined in terms of the existence of certain vertex partitions;graphs with polarity and monopolarity are respectively called polar and monopolar graphs. These two pro...
详细信息
Polarity and monopolarity are properties of graphs defined in terms of the existence of certain vertex partitions;graphs with polarity and monopolarity are respectively called polar and monopolar graphs. These two properties commonly generalize bipartite and split graphs, but are hard to recognize in general. In this article we identify two classes of graphs, triangle-free graphs and claw-free graphs, restricting to which provide novel impact on the complexity of the recognition problems. More precisely, we prove that recognizing polarity or monopolarity remains NP-complete for triangle-free graphs. We also show that for claw-free graphs the former is NP-complete and the latter is polynomialtime solvable. This is in sharp contrast to a recent result that both polarity and monopolarity can be recognized in linear time for line graphs. Our proofs for the NP-completeness are simple reductions. The polynomial time algorithm for recognizing the monopolarity of claw-free graphs uses a subroutine similar to the well-known breadth-first search algorithm and is based on a new structural characterization of monopolar claw-free graphs, a generalization of one for monopolar line graphs obtained earlier.
Deciding whether a digraph contains a pair of arc-disjoint in-and out-branchings rooted at a specified vertex is a well-known NP-complete problem (as proved by Thomassen, see [2]). This problem has been shown to be po...
详细信息
Deciding whether a digraph contains a pair of arc-disjoint in-and out-branchings rooted at a specified vertex is a well-known NP-complete problem (as proved by Thomassen, see [2]). This problem has been shown to be polynomialtime solvable for semicomplete digraphs [2] and for quasi-transitive digraphs [6]. In this article, we study the problem for locally semicomplete digraphs. We characterize locally semicomplete digraphs that contain a pair of arc-disjoint in-and out-branchings rooted at a specified vertex. Our proofs are constructive and imply the existence of a polynomial time algorithm for finding the desired branchings when they exist. Our results generalizes those from [2] for semicomplete digraphs and solves an open problem from [4]. (C) 2014 Wiley Periodicals, Inc.
This paper addresses the minmax regret 1-sink location problem on a dynamic flow path network with parametric weights. A dynamic flow path network consists of an undirected path with positive edge lengths, positive ed...
详细信息
This paper addresses the minmax regret 1-sink location problem on a dynamic flow path network with parametric weights. A dynamic flow path network consists of an undirected path with positive edge lengths, positive edge capacities, and nonnegative vertex weights. A path can be considered as a road, an edge length as the distance along the road, and a vertex weight as the number of people at the site. An edge capacity limits the number of people that can enter the edge per unit time. We consider the problem of locating a sink where all the people evacuate quickly. In our model, each weight is represented by a linear function of a common parameter t, and the decision maker who determines the sink location does not know the value of t. We formulate the problem under such uncertainty as the minmax regret problem. Given t and sink location x, the cost is the sum of arrival times at x for all the people determined by t. The regret for x under t is the gap between this cost and the optimal cost under t. The problem is to find the sink location minimizing the maximum regret over all t. For the problem, we propose an O(n42 alpha(n)alpha(n)2logn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n<^>4 2<^>{\alpha (n)} \alpha (n)<^>2 \log n)$$\end{document} timealgorithm, where n is the number of vertices in the network and alpha()\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha (\cdot )$$\end{document} is the inverse Ackermann function. Also, for the special case in which every edge has the same capacity, we show that the complexity can be reduced to O(n32 alpha(n)alpha(n)logn)\documentclass[12pt]{min
The maximum or minimum spanning tree problem is a classical combinatorial optimization problem. In this paper, we consider the partial inverse maximum spanning tree problem in which the weight function can only be dec...
详细信息
The maximum or minimum spanning tree problem is a classical combinatorial optimization problem. In this paper, we consider the partial inverse maximum spanning tree problem in which the weight function can only be decreased. Given a graph, an acyclic edge set, and an edge weight function, the goal of this problem is to decrease weights as little as possible such that there exists with respect to function containing the given edge set. If the given edge set has at least two edges, we show that this problem is APX-Hard. If the given edge set contains only one edge, we present a polynomial time algorithm.
We describe an algorithm for the high multiplicity asymmetric traveling salesman problem with feedback vertex set of size k (HMATSP-kFVS) where each vertex can be visited a certain number of times and each cycle in a ...
详细信息
We describe an algorithm for the high multiplicity asymmetric traveling salesman problem with feedback vertex set of size k (HMATSP-kFVS) where each vertex can be visited a certain number of times and each cycle in a solution contains at least one vertex from the feedback vertex set. We show how it can be used to improve algorithms in automated storage and retrieval systems. An automated storage and retrieval system includes storage blocks and storage and retrieval machines that either move to retrieve unit loads from their current locations in the system to a depot or take unit loads from a depot and store them to specific locations in the system. Given n storage and retrieval requests in a system with k depots and one storage and retrieval machine, we show that our algorithm for HMATSP-kFVS can solve the problem of minimizing total traveling time of the storage and retrieval machine in O(n(k) + n(3)) time when all depots are specialized (each depot fulfills one type of requests) and in O(n(2k) + n(3)) time when depots are regular (each depot fulfills both types of requests). The best previous algorithm only solves the special case of the problem with 2 regular depots in O(n(6)) time. The applicability of our algorithm for several generalizations and special cases of the problem is also discussed. Furthermore, to evaluate the performance of our solution method, we perform extensive numerical experiments. (C) 2020 Elsevier B.V. All rights reserved.
In this paper, the time-optimal velocity planning problem for five-axis computer numerical control machining along a given parametric tool path under chord error, acceleration, and jerk constraints is studied. The vel...
详细信息
In this paper, the time-optimal velocity planning problem for five-axis computer numerical control machining along a given parametric tool path under chord error, acceleration, and jerk constraints is studied. The velocity planning problem under confined chord error, feedrate, and acceleration is reduced to an equivalent linear programming problem by discretizing the tool path and other quantities. As a consequence, a polynomial time algorithm with computational complexity O(N (3.5)) is given to find the optimal solution, where N is the number of discretized segments of the tool path. The velocity planning problem under confined chord error, feedrate, acceleration, and jerk is reduced to a linear programming program by using a linear function to approximate the nonlinear jerk constraint. As a consequence, a polynomial time algorithm is given to find the approximate time-optimal solution. Simulation results are used to show the efficiency and effectiveness of the algorithms.
The traveling salesman problem (TSP) belongs to the most basic, most important, and most investigated problems in combinatorial optimization. Although it is an NP-hard problem, many of its special cases can be solved ...
详细信息
The traveling salesman problem (TSP) belongs to the most basic, most important, and most investigated problems in combinatorial optimization. Although it is an NP-hard problem, many of its special cases can be solved efficiently in polynomialtime. We survey these special cases with emphasis on the results that have been obtained during the decade 1985-1995. This survey complements an earlier survey from 1985 compiled by Gilmore, Lawler, and Shmoys [The Traveling Salesman Problem-A Guided Tour of Combinatorial Optimization, Wiley, Chichester, pp. 87-143].
We consider the algorithmic problem of computing Cartan subalgebras in Lie algebras over finite fields and algebraic number fields. We present a deterministic polynomial time algorithm for the case when the ground fie...
详细信息
We consider the algorithmic problem of computing Cartan subalgebras in Lie algebras over finite fields and algebraic number fields. We present a deterministic polynomial time algorithm for the case when the ground field k is sufficiently large. Our method is based on a solution of a linear algebra problem: the task of finding a locally regular element in a subspace of linear transformations. Also, we give a polynomial time algorithm for restricted Lie algebras over arbitrary finite fields. Both methods require an auxiliary procedure for finding non-nilpotent elements in subalgebras. This problem is also treated. Computational experiences are discussed at the end of the paper.
作者：
Amoura, AKLRI
Bât. 490 Université Paris Sud 91405 Orsay Cedex France
A recent extension of the standard model, the so called multiprocessor task system, is discussed. According to this model, some tasks have to be executed on more than one processor at a time. Scheduling multiprocess...
详细信息
A recent extension of the standard model, the so called multiprocessor task system, is discussed. According to this model, some tasks have to be executed on more than one processor at a time. Scheduling multiprocessor tasks on m parallel processors in the presence of precedence constraints are discussed. Tasks are supposed to have all the same length (unit-length) and require either one or m processors for their processing. The objective of the problem is the minimization of the makespan. It is proved that any optimal scheduling algorithm for P subscript m p subscript j equals 1, prec C subscript max, i.e., the classical model, can be (efficiently) used to solve P subscript m size subscript j is an element of (1,m), p subscript j equals 1, prec C subscript max. In addition, some polynomially solvable classes of precedence graphs are derived. It is also demonstrated that no (significant) polynomial extension of this result can be expected.
We consider a special case of the unbounded knapsack problem that is characterized by a set of simple inequalities that relate item weights to item costs. We present an algorithm for this special case with time comple...
详细信息
We consider a special case of the unbounded knapsack problem that is characterized by a set of simple inequalities that relate item weights to item costs. We present an algorithm for this special case with time complexity linear in the number of items. (C) 2001 Published by Elsevier Science B.V.
暂无评论