We prove that every digraph of circumference l has DAG-width at most l. This is best possible and solves a recent conjecture from S. Kintali (ArXiv:1401.2662v1 [***], January 2014).(1) As a consequence of this result ...
详细信息
We prove that every digraph of circumference l has DAG-width at most l. This is best possible and solves a recent conjecture from S. Kintali (ArXiv:1401.2662v1 [***], January 2014).(1) As a consequence of this result we deduce that the k-linkage problem is polynomially solvable for every fixed k in the class of digraphs with bounded circumference. This answers a question posed in J. Bang-Jensen, F. Havet, and A. K. Maia (Theor Comput Sci 562 (2014), 283-303). We also prove that the weak k-linkage problem (where we ask for arc-disjoint paths) is polynomially solvable for every fixed k in the class of digraphs with circumference 2 as well as for digraphs with a bounded number of disjoint cycles each of length at least 3. The case of bounded circumference digraphs is still open. Finally, we prove that the minimum spanning strong subdigraph problem is NP-hard on digraphs of DAG-width at most 5.
We study the maximum node-weighted induced bipartite subgraph problem in planar graphs with maximum degree three. We show that this is polynomially solvable. It was shown in Choi, Nakajima, and Rim [SIAM J. Discrete M...
详细信息
We study the maximum node-weighted induced bipartite subgraph problem in planar graphs with maximum degree three. We show that this is polynomially solvable. It was shown in Choi, Nakajima, and Rim [SIAM J. Discrete Math., 2 (1989), pp. 38-47] that it is NP-complete if the maximum degree is four. We extend these ideas to the problem of balancing signed graphs. We also consider maximum weighted induced acyclic subgraphs of planar directed graphs. If the maximum degree is three, it is easily shown that this is polynomially solvable. We show that for planar graphs with maximum degree four the same problem is NP-complete.
In this paper we introduce a polynomial algorithm for the recognition of weakly nonnegative unit forms. The algorithm identify hypercritical restrictions testing every 9-point subset of the quadratic form associated g...
详细信息
The concept of arc-disjoint flows in networks was recently introduced in Bang-Jensen and Bessy (2014). This is a very general framework within which many well-known and important problems can be formulated. In particu...
详细信息
The concept of arc-disjoint flows in networks was recently introduced in Bang-Jensen and Bessy (2014). This is a very general framework within which many well-known and important problems can be formulated. In particular, the existence of arc-disjoint branching flows, that is, flows which send one unit of flow from a given source s to all other vertices, generalizes the concept of arc-disjoint out-branchings (spanning out-trees) in a digraph. A pair of out-branchings B-s,1(+), B-s,2(+) from a roots in a digraph D = (V, A) on n vertices corresponds to arc-disjoint branching flows x(1), x(2) (the arcs carrying flow in x(i) are those used in B-s,i(+) = 1, 2) in the network that we obtain from D by giving all arcs capacity n - 1. It is then a natural question to ask how much we can lower the capacities on the arcs and still have, say, two arc-disjoint branching flows from the given root s. We prove that for every fixed integer k >= 2 it is an NP-complete problem to decide whether a network N = (V, A, u) where u(ij) = k for every arc ij has two arc-disjoint branching flows rooted at s. a polynomial problem to decide whether a network N = (V, A, u) on n vertices and u(ij) = n - k for every arc ij has two arc-disjoint branching flows rooted at s. The algorithm for the later result generalizes the polynomial algorithm, due to Lovasz, for deciding whether a given input digraph has two arc-disjoint out-branchings rooted at a given vertex. Finally we prove that under the so-called Exponential Time Hypothesis (ETH), for every epsilon > 0 and for every k(n) with (log(n))(1+epsilon) <= k(n) <= n/2 (and for every large i we have k(n) = i for some n) there is no polynomial algorithm for deciding whether a given digraph contains two arc-disjoint branching flows from the same root so that no arc carries flow larger than n - k(n). (C) 2015 Elsevier B.V. All rights reserved.
Given a digraph D = (V, A) and a positive integer k, a subset B subset of A is called a k-arborescence, if it is the disjoint union of k spanning arborescences. When also arc-costs c : A -> R are given, minimizing ...
详细信息
Given a digraph D = (V, A) and a positive integer k, a subset B subset of A is called a k-arborescence, if it is the disjoint union of k spanning arborescences. When also arc-costs c : A -> R are given, minimizing the cost of a k-arborescence is well-known to be tractable. In this paper we take on the following problem: what is the minimum cardinality of a set of arcs the removal of which destroys every minimum c-cost karborescence. Actually, the more general weighted problem is also considered, that is, arc weights w : A -> R+ (unrelated to c) are also given, and the goal is to find a minimum weight set of arcs the removal of which destroys every minimum c-cost k-arborescence. An equivalent version of this problem is where the roots of the arborescences are fixed in advance. In an earlier paper (Bernath and Pap, 2013) we solved this problem for k = 1. This work reports on other partial results on the problem. We solve the case when both c and w are uniform-that is, find a minimum size set of arcs that covers all k-arborescences. Our algorithm runs in polynomial time for this problem. The solution uses a result of Barasz et al. (2005) saying that the family of so-called in-solid sets (sets with the property that every proper subset has a larger in-degree) satisfies the Helly-property, and thus can be (efficiently) represented as a subtree hypergraph. We also give an algorithm for the case when only c is uniform but w is not. This algorithm is only polynomial if k is not part of the input. (C) 2016 Published by Elsevier B.V.
In this article, we define two different workforce leveling objectives for serial transfer lines. Each job is to be processed on each transfer station for c time periods (e.g., hours). We assume that the number of wor...
详细信息
In this article, we define two different workforce leveling objectives for serial transfer lines. Each job is to be processed on each transfer station for c time periods (e.g., hours). We assume that the number of workers needed to complete each operation of a job in precisely c periods is given. Jobs transfer forward synchronously after every production cycle (i.e., c periods). We study two leveling objectives: maximin workforce size (W-m) and min range (R). Leveling objectives produce schedules where the cumulative number of workers needed in all stations of a transfer line does not experience dramatic changes from one production cycle to the next. For W-m and a two-station system, we develop a fast polynomial algorithm. The range problem is known to be NP-complete. For the two-station system, we develop a very fast optimal algorithm that uses a tight lower bound and an efficient procedure for finding complementary Hamiltonian cycles in bipartite graphs. Via a computational experiment, we demonstrate that range schedules are superior because not only do they limit the workforce fluctuations from one production cycle to the next, but they also do so with a minor increase in the total workforce size. We extend our results to the m-station system and develop heuristic algorithms. We find that these heuristics work poorly for min range (R), which indicates that special structural properties of the m-station problem need to be identified before we can develop efficient algorithms. (C) 2016 Wiley Periodicals, Inc.
In the article the problem of finding the maximum multiple flow in the network of any natural multiplicity is studied. There are arcs of three types: ordinary arcs, multiple arcs and multi-arcs. Each multiple and mult...
详细信息
In the article the problem of finding the maximum multiple flow in the network of any natural multiplicity is studied. There are arcs of three types: ordinary arcs, multiple arcs and multi-arcs. Each multiple and multi-arc is a union of linked arcs, which are adjusted with each other. The network constructing rules are described. The definitions of a divisible network and some associated subjects are stated. The important property of the divisible network is that every divisible network can be partitioned into parts, which are adjusted on the linked arcs of each multiple and multi-arc. Each part is the ordinary transportation network. The main results of the article are the following subclasses of the problem of finding the maximum multiple flow in the divisible network. 1. The divisible networks with the multi-arc constraints. Assume that only one vertex is the ending vertex for a multi-arc in network parts. In this case the problem can be solved in a polynomial time. 2. The divisible networks with the weak multi-arc constraints. Assume that only one vertex is the ending vertex for a multi-arc in network parts (1 <= s < k - 1) and other parts have at least two such vertices. In that case the multiplicity of the maximum multiple flow problem can be decreased to k - s. 3. The divisible network of the parallel structure. Assume that the divisible network component, which consists of all multiple arcs, can be partitioned into subcomponents, each of them containing exactly one vertex-beginning of a multi-arc. Suppose that intersection of each pair of subcomponents is the only vertex-network source x(0). If k = 2, the maximum flow problem can be solved in a polynomial time. If k >= 3, the problem is NP-complete. The algorithms for each polynomial subclass are suggested. Also, the multiplicity decreasing algorithm for the divisible network with weak multi-arc constraints is formulated.
We study a dual-mode production planning problem with emission constraints, where a manufacturer produces a single product with two optional technologies. The manufacturer is equipped with the regular and green techno...
详细信息
We study a dual-mode production planning problem with emission constraints, where a manufacturer produces a single product with two optional technologies. The manufacturer is equipped with the regular and green technologies to comply with emission limitations, and either one or both can be adopted for production. We first investigate the problem under a mandatory emission-cap policy and then extend it to consider emission trading under an emission cap-and-trade scheme. Based on the structural properties of the problem and a multi-level decomposition approach, a polynomial dynamic programming algorithm is developed to solve the models optimally. Our analysis shows that the manufacturer should only use a mix of both technologies when the emission cap is a binding constraint. Numerical results show that the manufacturer's decisions and benefits are significantly affected by the emission cap under the mandatory emission-cap policy, especially when the cap is at a relatively low level. However, the carbon price may not remarkably affect the manufacturer's cost because its influence could be abated through the flexible technology switch under the emission cap-and-trade scheme. (C) 2015 Elsevier B.V. All rights reserved.
The Eulerian Editing problem asks, given a graph G and an integer k, whether G can be modified into an Eulerian graph using at most k edge additions and edge deletions. We show that this problem is polynomial-time sol...
详细信息
The Eulerian Editing problem asks, given a graph G and an integer k, whether G can be modified into an Eulerian graph using at most k edge additions and edge deletions. We show that this problem is polynomial-time solvable for both undirected and directed graphs. We generalize these results for problems with degree parity constraints and degree balance constraints, respectively. We also consider the variants where vertex deletions are permitted. Combined with known results, this leads to full complexity classifications for both undirected and directed graphs and for every subset of the three graph operations. (C) 2015 Elsevier Inc. All rights reserved.
In this paper, a generalized formulation of a classical single machine scheduling problem is considered. A set of n jobs characterized by their release dates, deadlines and a start time-dependent processing time funct...
详细信息
暂无评论