Search

Abstract: This paper introduces a stochastic scheduling problem. In this problem a directed acyclic graphs (DAG) represents the precedence relations among tasks that workers are scheduled to execute. The question is to find a schedule such that if tasks are assigned to workers according to , the expected time needed to execute all the tasks is minimized. The time needed to execute task by worker is a random variable expressed by a negative exponential distribution with parameter and each task can be executed by more than one worker at a time. In this paper, we will prove that the problem in its general form is NP-hard, but when the DAG width is constant, we will show that the optimum schedules can be found in polynomial time. [Copyright &y& Elsevier]

Abstract: In this paper, we consider the evacuation problem in a network which consists of a directed graph with capacities and transit times on its arcs. This problem can be solved by the algorithm of Hoppe and Tardos [B. Hoppe, É. Tardos, The quickest transshipment problem, Math. Oper. Res. 25(1) (2000) 36–62] in polynomial time. However their running time is high-order polynomial, and hence is not practical in general. Thus, it is necessary to devise a faster algorithm for a tractable and practically useful subclass of this problem. In this paper, we consider a network with a sink such that (i) for each vertex the sum of the transit times of arcs on any path from to takes the same value, and (ii) for each vertex the minimum - cut is determined by the arcs incident to whose tails are reachable from . This class of networks is a generalization of grid networks studied in the paper [N. Kamiyama, N. Katoh, A. Takizawa, An efficient algorithm for evacuation problem in dynamic network flows with uniform arc capacity, IEICE Trans. Infrom. Syst. E89-D (8) (2006) 2372–2379]. We propose an efficient algorithm for this network problem. [Copyright &y& Elsevier]

Abstract: In this paper, we obtain a generalized Lucas polynomial sequence from the lattice paths for the Delannoy numbers by allowing weights on the steps and . These weighted lattice paths lead us to a combinatorial interpretation for such a Lucas polynomial sequence. The concept of Riordan arrays is extensively used throughout this paper. [Copyright &y& Elsevier]

Abstract: Let be a non-trivial, loopless graph and for each non-trivial subgraph of , let . The graph is 1-balanced if , the maximum among , taken over all non-trivial subgraphs of , is attained when . This quantity is called the fractional arboricity of the graph . The value appears in a paper by Picard and Queyranne and has been studied extensively by Catlin, Grossman, Hobbs and Lai. The quantity measures how much a given graph differs from being 1-balanced. In this paper, we describe a systematic method of modifying a given graph to obtain a 1-balanced graph on the same number of vertices and edges. We obtain this by a sequence of iterations; each iteration re-defining one end-vertex of an edge in the given graph. After each iteration, either the value of the new graph formed is less than that of the graph from the previous iteration or the size of the maximal -achieving subgraph of the new graph is smaller than that of the graph in the previous iteration. We show that our algorithm is polynomial in time complexity. Further ways to decrease the number of iterations are also discussed. [Copyright &y& Elsevier]

Linear feedback shift registers (LFSRs) play a significant role in communications security and we investigate design of a selected class of word-based LFSRs known as σ -LFSRs. Both the search algorithm and the construction algorithm generate efficient primitive σ -LFSRs. The search algorithm first constructs the σ -polynomial and then checks the primitiveness of the σ -polynomial, whereas the construction algorithm for the σ -LFSR, first finds a primitive polynomial f ( x ) and then constructs the primitive σ -LFSR from f ( x ) . In this paper, we present some novel results pertaining to the search algorithm for primitive σ -LFSR along with the exhaustive search space complexity of the search algorithm for σ -LFSRs. Then we investigate and compare the performance of the construction algorithm with the search algorithm for the primitive σ -LFSR. Finally, the number of σ -LFSRs similar to the σ -LFSRs generated by the construction algorithm is provided. [ABSTRACT FROM AUTHOR]

A pseudoforest is a graph where each connected component contains at most one cycle, or alternatively, a graph that can be turned into a forest by removing at most one edge from each connected component. In this paper, we show that the following problem can be solved in O ( 3 k n k O ( 1 ) ) time: given a graph G and an integer k , can we delete at most k vertices from G such that we obtain a pseudoforest? The result improves upon an earlier result by Philip et al. (2015) who gave a (nonlinear) 7 . 5 6 k n O ( 1 ) -time algorithm both in the exponential factor depending on k as well as in the polynomial factor depending on n . [ABSTRACT FROM AUTHOR]

Abstract: This paper is a note on “Complexity analysis of job-shop scheduling with deteriorating jobs” [G. Mosheiov, Complexity analysis of job-shop scheduling with deteriorating jobs, Discrete Applied Mathematics 117 (2002) 195–209]. A proportional deterioration rate is assumed and the objective is the minimization of the makespan. Mosheiov presents NP-hardness results for flow-shops and open-shops with three or more machines and for job-shops with two or more machines. The proof of NP-hardness for the flow-shop case is however not correct. This paper provides a correct proof. [ABSTRACT FROM AUTHOR]

With the proliferation of multi-gantry automated stacking cranes, the already difficult crane scheduling problem in container terminals has become even more challenging. In this paper we present an efficient algorithm that can solve a sub-problem that arises in this context, namely the prioritization of crane gantry movements once transportation tasks have been assigned. We tackle this problem for both, twin crane setting and crossover crane setting, and develop graphical models and strongly polynomial algorithms accordingly. A series of experiments is carried out where it is shown that the method can produce optimum solutions with exceptionally small run times. [ABSTRACT FROM AUTHOR]

Abstract: This paper investigates the Steiner Tree Problem with Delays (STPD), a variation of the classical Steiner Tree problem that arises in multicast routing. We propose an exact solution approach that is based on a polynomial-size formulation for this challenging NP-hard problem. The LP relaxation of this formulation is enhanced through the derivation of new lifted Miller–Tucker–Zemlin subtour elimination constraints. Furthermore, we present several preprocessing techniques for both reducing the problem size and tightening the LP relaxation. Finally, we report the results of extensive computational experiments on instances with up to 1000 nodes. These results attest to the efficacy of the combination of the enhanced formulation and reduction techniques. [Copyright &y& Elsevier]

Abstract: Let be positive integers. A -edge-colored graph is -e.c. or -existentially closed if for any disjoint sets of vertices with , there is a vertex not in such that all edges from this vertex to the set are colored by the -th color. In this paper, we give an explicit construction of a -e.c. graph of polynomial order. [Copyright &y& Elsevier]

Abstract: In this paper, we determine explicitly the zeta polynomials of near-MDS codes and obtain necessary and sufficient conditions for near-MDS codes to satisfy the Riemann hypothesis analogue. [Copyright &y& Elsevier]

Abstract: In this paper, we consider two location problems of determining the best location of roots of arc-disjoint arborescences in a network. In the first problem, we are given prescribed vertex subsets and the problem asks for finding the best location of roots of arc-disjoint arborescences that span these vertex subsets. We show that this problem is -hard in general and that it can be solved in polynomial time in the case where the prescribed vertex subsets are convex. In the second problem, we are given a demand for each vertex and the problem asks for finding the best location of roots of arc-disjoint arborescences such that each vertex is contained in at least arborescences. We show that this problem is -hard in general. [Copyright &y& Elsevier]

Abstract: In this paper, we study connected plane graphs with link component number equal to the nullity and call them near-extremal graphs. We first study near-extremal graphs with minimum degree at least 3 and prove that a connected plane graph with minimum degree at least 3 is a near-extremal graph if and only if is isomorphic to , the complete graph with 4 vertices. The result is obtained by studying general graphs using the knowledge of bicycle space and the Tutte polynomial. Then a simple algorithm is given to judge whether a connected plane graph is a near-extremal graph or not. Finally we study the construction of near-extremal graphs and prove that all near-extremal graphs can be constructed from a loop and by two graph operations. [Copyright &y& Elsevier]

Abstract: The measure and conquer approach has proven to be a powerful tool to analyse exact algorithms for combinatorial problems like Dominating Set and Independent Set. This approach is used in this paper to obtain a faster exact algorithm for Dominating Set. We obtain this algorithm by considering a series of branch and reduce algorithms. This series is the result of an iterative process in which a mathematical analysis of an algorithm in the series with measure and conquer results in a convex or quasiconvex programming problem. The solution, by means of a computer, to this problem not only gives a bound on the running time of the algorithm, but can also give an indication on where to look for a new reduction rule, often giving a new, possibly faster algorithm. As a result, we obtain an time and polynomial space algorithm. [Copyright &y& Elsevier]

Abstract: Determining the cells of an arrangement of hyperplanes is a classical problem in combinatorial geometry. In this paper we present an efficient recursive procedure to solve it. In fact, by considering a connection between the latter problem and optimality conditions of unconstrained quadratic optimization problems in the following form: , with , we can show the proposed algorithm solves problems of the form in polynomial time when the rank of the matrix is fixed and the number of its positive diagonal entries is . [Copyright &y& Elsevier]

Abstract: A graph is polar if the vertex set can be partitioned into and in such a way that induces a complete multipartite graph and induces a disjoint union of cliques (i.e., the complement of a complete multipartite graph). Polar graphs naturally generalize several classes of graphs such as bipartite graphs, cobipartite graphs and split graphs. Recognizing polar graphs is an NP-complete problem in general, and thus it is of interest to restrict the problem to special classes of graphs. Cographs and chordal graphs are among those whose polarity can be recognized in polynomial time. The line-graphs of bipartite graphs are another class of graphs whose polarity has been characterized recently in terms of forbidden subgraphs, but no polynomial time algorithm is given. In this paper, we present an algorithm which decides whether the line-graph of an input bipartite graph is polar and constructs a polar partition when one exists. [ABSTRACT FROM AUTHOR]

Abstract: This paper revisits the ‘branchwidth territories’ of Kloks, Kratochvíl and Müller [T. Kloks, J. Kratochvíl, H. Müller, New branchwidth territories, in: 16th Ann. Symp. on Theoretical Aspect of Computer Science, STACS, in: Lecture Notes in Computer Science, vol. 1563, 1999, pp. 173–183] to provide a simpler proof, and a faster algorithm for computing the branchwidth of an interval graph. We also generalize the algorithm to the class of chordal graphs, albeit at the expense of exponential running time. Compliance with the ternary constraint of the branchwidth definition is facilitated by a simple new tool called -troikas: three sets of size at most each are a -troika of set , if any two have union . We give a straightforward algorithm, computing branchwidth for an interval graph on edges, vertices and maximal cliques. We also prove a conjecture of Mazoit [F. Mazoit, A general scheme for deciding the branchwidth, Technical Report RR2004-34, LIP — École Normale Supérieure de Lyon, 2004. http://www.ens-lyon.fr/LIP/Pub/Rapports/RR/RR2004/RR2004-34.pdf], by showing that branchwidth can be computed in polynomial time for a chordal graph given with a clique tree having a polynomial number of subtrees. [Copyright &y& Elsevier]

Abstract: Graph searching was introduced by Parson [T. Parson, Pursuit-evasion in a graph, in: Theory and Applications of Graphs, in: Lecture Notes in Mathematics, Springer-Verlag, 1976, pp. 426–441]: given a “contaminated” graph (e.g., a network containing a hostile intruder), the search number of the graph is the minimum number of searchers needed to “clear” the graph (or to capture the intruder). A search strategy is connected if, at every step of the strategy, the set of cleared edges induces a connected subgraph. The connected search number of a graph is the minimum such that there exists a connected search strategy for the graph using at most searchers. This paper is concerned with the ratio between the connected search number and the search number. We prove that, for any chordal graph of treewidth , . More precisely, we propose a polynomial-time algorithm that, given any chordal graph , computes a connected search strategy for using at most searchers. Our main tool is the notion of connected tree-decomposition. We show that, for any connected graph of chordality , there exists a connected search strategy using at most searchers where is an optimal tree-decomposition of . [Copyright &y& Elsevier]

Abstract: A Directed Path Family is a family of subsets of some finite ground set whose members can be realized as arc sets of simple directed paths in some directed graph. In this paper we show that recognizing whether a given family is a Directed Path family is an NP-Complete problem, even when all members in the family have at most two elements. If instead of a family of subsets, we are given a collection of words from some finite alphabet, then deciding whether there exists a directed graph such that each word in the language is the set of arcs of some path in , is a polynomial-time solvable problem. [Copyright &y& Elsevier]

Abstract: This paper deals with the maximum triangle packing problem. For this problem, Hassin and Rubinstein gave a randomized polynomial-time approximation algorithm that achieves an expected ratio of for any constant . By modifying their algorithm, we obtain a new randomized polynomial-time approximation algorithm for the problem which achieves an expected ratio of for any constant . [Copyright &y& Elsevier]

Abstract: This paper deals with the complexity of the decomposition of a digital surface into digital plane segments (DPSs for short). We prove that the decision problem (does there exist a decomposition with less than DPSs?) is NP-complete, and thus that the optimization problem (finding the minimum number of DPSs) is NP-hard. The proof is based on a polynomial reduction of any instance of the well-known 3-SAT problem to an instance of the digital surface decomposition problem. A geometric model for the 3-SAT problem is proposed. [Copyright &y& Elsevier]

Abstract: In this paper, we study the relationship between the approximability and the parameterized complexity of NP optimization problems. We introduce a notion of polynomial fixed-parameter tractability and prove that, under a very general constraint, an NP optimization problem has a fully polynomial time approximation scheme if and only if the problem is polynomial fixed-parameter tractable. By enforcing a constraint of planarity on the W-hierarchy studied in parameterized complexity theory, we obtain a class of NP optimization problems, the planar W-hierarchy, and prove that all problems in this class have efficient polynomial time approximation schemes (EPTAS). The planar W-hierarchy seems to contain most of the known EPTAS problems, and is significantly different from the class introduced by Khanna and Motwani in their efforts in characterizing optimization problems with polynomial time approximation schemes. [Copyright &y& Elsevier]

Combinatorial Laplace operators on the simplicial complex of independent sets of a loopless matroid M are known to have non-negative integral spectra (J. Amer. Math. Soc. B 13 (2000) 129). The spectrum polynomial of M, a polynomial in two variables formulated via the flats of M, is a generating function for the spectra of these operators. In this paper, we establish recurrence formulas for the spectrum polynomial of a matroid, analogous to the deletion–contraction recursions for the Tutte polynomial. However, we show that for any matroid M and e∈M the new formulas for the spectrum polynomial depend on whether or not e is closed in M. In particular, the spectrum polynomial is a new invariant for matroids that is not a Tutte–Grothendieck invariant. [Copyright &y& Elsevier]