The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.

1.

Asratian, Armen

et al.

Linköping University, Department of Mathematics, Mathematics and Applied Mathematics. Linköping University, Faculty of Science & Engineering.

Casselgren, Carl Johan

Linköping University, Department of Mathematics, Mathematics and Applied Mathematics. Linköping University, Faculty of Science & Engineering.

Petrosyan, Petros A.

Yerevan State Univ, Armenia; Natl Acad Sci, Armenia.

Cyclic deficiency of graphs2019In: Discrete Applied Mathematics, ISSN 0166-218X, E-ISSN 1872-6771, Vol. 266, p. 171-185Article in journal (Refereed)

Abstract [en]

A proper edge coloring of a graph G with colors 1, 2, . . . , t is called a cyclic interval t-coloring if for each vertex v of G the edges incident to v are colored by consecutive colors, under the condition that color 1 is considered as consecutive to color t. In this paper we introduce and investigate a new notion, the cyclic deficiency of a graph G, defined as the minimum number of pendant edges whose attachment to G yields a graph admitting a cyclic interval coloring; this number can be considered as a measure of closeness of G of being cyclically interval colorable. We determine or bound the cyclic deficiency of several families of graphs. In particular, we present examples of graphs of bounded maximum degree with arbitrarily large cyclic deficiency, and graphs whose cyclic deficiency approaches the number of vertices. Finally, we conjecture that the cyclic deficiency of any graph does not exceed the number of vertices, and we present several results supporting this conjecture. (C) 2018 Elsevier B.V. All rights reserved.

The full text will be freely available from 2020-12-31 15:04

We consider the problem of estimating optima of covering integer linear programs with 0-1 variables under the following conditions: we do not know exact values of elements in the constraint matrix A but we know what elements of A are zero and what are nonzero, and also know minimal and maximal values of nonzero elements. We find bounds for variation of the optima of such programs in the worst and average cases. We also find some conditions guaranteeing that the variation of the optimum of such programs in the average case is close to 1 as the number of variables tends to infinity. This means that the values of nonzero elements in A can vary without significantly affecting the value of the optimum of the integer program.

We study the complexity of finding 2-factors with various restrictions as well as edge-decompositions in (the underlying graphs of) digraphs. In particular we show that it is N P-complete to decide whether the underlying undirected graph of a digraph D has a 2-factor with cycles C-1, C-2, ..., C-k such that at least one of the cycles C-i is a directed cycle in D (while the others may violate the orientation back in D). This solves an open problem from J. Bang-Jensen et al., Vertex-disjoint directed and undirected cycles in general digraphs, JCT B 106 (2014), 1-14. Our other main result is that it is also N P-complete to decide whether a 2-edge-colored bipartite graph has two edge-disjoint perfect matchings such that one of these is monochromatic (while the other does not have to be). We also study the complexity of a number of related problems. In particular we prove that for every even k greater than= 2, the problem of deciding whether a bipartite digraph of girth k has a k-cycle-free cycle factor is N P-complete. Some of our reductions are based on connections to Latin squares and so-called avoidable arrays.

Let C-1 and C-2 be two sets of cycles. We determine all generalised Ramsey numbers R(C-1, C-2) such that C-1 or C-2 contains a cycle of length at most 6. This generalises previous results of Erdos, Faudree, Rosta, Rousseau, and Schelp. Furthermore, we give a conjecture for the general case. We also provide a complete classification of most (C-1, C-2)-critical graphs such that C-1 or C-2 contains a cycle of length at most 5. For length 4, this is an easy extension of a recent result of Wu, Sun, and Radziszowski, in which vertical bar C-1 vertical bar = vertical bar C-2 vertical bar = 1. For lengths 3 and 5, our results are new also in this special case. (C) 2017 Elsevier B.V. All rights reserved.

In this paper the two-stage knapsack problem with random weights is studied under the aspect of approximability. We assume finite probability distributions for the weights and show that, unless P = NP, the so obtained problem cannot be approximated in polynomial time within a better ratio than K-1/2 (where K is the number of second-stage scenarios). We further study the special cases where in the second stage items can only be added or only be removed, but not both. Positive approximation results are given for three particular cases, namely linearly dependent first- and second-stage rewards, the polynomial scenario model and the case where the number of scenarios is assumed to be a constant. To the best of our knowledge, this is the first study of a two-stage knapsack problem under the aspect of approximability and the first time a non-approximability result has been proven for a stochastic knapsack problem of any kind.

Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory.

Given an undirected graph with edge costs and both revenues and weights on the vertices, the traveling salesman subtour problem is to find a subtour that includes a depot vertex, satisfies a knapsack constraint on the vertex weights, and that minimizes edge costs minus vertex revenues along the subtour.

We propose a decomposition scheme for this problem. It is inspired by the classic side-constrained 1-tree formulation of the traveling salesman problem, and uses stabilized column generation for the solution of the linear programming relaxation. Further, this decomposition procedure is combined with the addition of variable upper bound (VUB) constraints, which improves the linear programming bound. Furthermore, we present a heuristic procedure for finding feasible subtours from solutions to the column generation problems. An extensive experimental analysis of the behavior of the computational scheme is presented.