Journal of Combinatorial Optimization

In this paper we consider the maximization of the weighted number of early jobs on a single machine with non-availability constraints. We deal with the resumable and the non-resumable cases. We show that the resumable version of this problem has a fully ...

A grid computing system consists of a group of programs and resources that are spread across machines in the grid. A grid system has a dynamic environment and decentralized distributed resources, so it is important to provide efficient scheduling for ...

In this contribution, we first investigate sharp bounds for the reciprocal sum-degree distance of graphs with a given matching number. The corresponding extremal graphs are characterized completely. Then we explore the $$k$$k-decomposition for the ...

In this paper, we study the approximation complexity of the Minimum Integral Solution Problem with Preprocessing introduced by Alekhnovich et al. (FOCS, pp. 216---225, 2005). We show that the Minimum Integral Solution Problem with Preprocessing over $$\...

Let $$D$$D be a finite and simple digraph with vertex set $$V(D)$$V(D) and arc set $$A(D)$$A(D). A signed Roman dominating function (SRDF) on the digraph $$D$$D is a function $$f:V(D)\rightarrow \{-1,1,2\}$$f:V(D) {-1,1,2} satisfying the conditions that ...

Let $$G=(V_G, E_G)$$G=(VG,EG) be a simple connected graph. The reciprocal degree distance of $$G$$G is defined as $$\bar{R}(G)=\sum _{\{u,v\}\subseteq V_G}(d_G(u)+d_G(v))\frac{1}{d_G(u,v)}=\sum _{u\in V_G}d_G(u)\hat{D}_G(u),$$R (G)= {u,v}⊆VG(dG(u)+dG(v))...

We present a new lifting approach for strengthening arbitrary clique tree inequalities that are known to be facet defining for the symmetric traveling salesman problem in order to get stronger valid inequalities for the symmetric quadratic traveling ...

Our main objective in this paper is to study the possible benefits of using task replication when generating a schedule in a desktop grid. We consider the problem of constructing a schedule in an environment where machines' speeds may be unpredictable ...

Considering the customer psychology while waiting to be served, we introduce a more reasonable form of deadlines into online traveling salesman problem (OL-TSP) with service flexibility. The salesman can choose whether to serve or not when a new request ...

Given an undirected graph with edge costs, the power of a node is the maximum cost of an edge incident to it, and the power of a graph is the sum of the powers of its nodes. Motivated by applications in wireless networks, we consider the following ...

A graph $$G$$G is diameter $$2$$2-critical if its diameter is two and the deletion of any edge increases the diameter. Murty and Simon conjectured that the number of edges in a diameter-$$2$$2-critical graph $$G$$G of order $$n$$n is at most $$\lfloor n^...

Given a graph $$G=(V,E)$$G=(V,E), Alice and Bob, alternate their turns in choosing uncoloured edges to be coloured. Whenever an uncoloured edge is chosen, it is coloured by the least positive integer not used by any of its coloured neighbours. Alice's ...

The Bandpass-2 problem is a variant of the maximum traveling salesman problem arising from optical communication networks using wavelength-division multiplexing technology, in which the edge weights are dynamic rather than fixed. The previously best ...

Let $$d_1, d_2,\ldots ,d_k$$d1,d2, ,dk be $$k$$k non-negative integers. A graph $$G$$G is $$(d_1,d_2,\ldots ,d_k)$$(d1,d2, ,dk)-colorable, if the vertex set of $$G$$G can be partitioned into subsets $$V_1,V_2,\ldots ,V_k$$V1,V2, ,Vk such that the ...

Relaxation techniques play a great role in solving the quadratic assignment problem, among which the convex quadratic programming bound (QPB) is competitive with existing bounds in the trade-off between cost and quality. In this article, we propose two ...

The concept of 2-rainbow domination of a graph $$G$$G coincides with the ordinary domination of the prism $$G\Box K_{2}$$G K2 (see Brešar et al., Taiwan J Math 12:213---225, 2008). Hence $$\gamma _{r2}(C_{m}\Box C_{n})\ge \frac{mn}{3}$$ r2(Cm Cn) mn3. ...

A total [k]-coloring of a graph $$G$$G is a mapping $$\phi : V (G) \cup E(G)\rightarrow [k]=\{1, 2,\ldots , k\}$$ :V(G) E(G) [k]={1,2, ,k} such that any two adjacent or incident elements in $$V (G) \cup E(G)$$V(G) E(G) receive different colors. Let $$f(...

Lovász and Schrijver introduced several lift and project methods for 0---1 integer programs, now collectively known as Lovász---Schrijver (LS) hierarchies. Several lower bounds have since been proven for the rank of various linear programming ...

This paper describes libbrkga, a GNU-style dynamic shared Python/C++ library of the biased random-key genetic algorithm (BRKGA) for bound constrained global optimization. BRKGA (J Heuristics 17:487---525, 2011b) is a general search metaheuristic for ...

This paper studies co-k-plex vertex partitions and more specifically co-2-plex vertex partitions. Co-$$k$$k-plexes and $$k$$k-plexes were first introduced in 1978 in the context of social network analysis. However, the study of co-k-plex vertex ...

We introduce A$$^3$$3CS, an adaptive framework with approximation guarantees for quickly identifying community structure in dynamic networks via maximizing Modularity Q. Our framework explores the advantages of the power-law distribution property found ...

The data arrangement problem on regular trees (DAPT) consists in assigning the vertices of a given graph G to the leaves of a d-regular tree T such that the sum of the pairwise distances of all pairs of leaves in T which correspond to edges of G is ...

An $$L(j,k)$$L(j,k)-labeling of a graph is a vertex labeling such that the difference of the labels of any two adjacent vertices is at least $$j$$j and that of any two vertices of distance $$2$$2 is at least $$k$$k. The minimum span of all $$L(j,k)$$L(j,...

A remarkable connection between the order of a maximum clique and the Lagrangian of a graph was established by Motzkin and Straus in Can J Math 17:533---540 (1965). This connection and its extensions were successfully employed in optimization to provide ...

In this paper, we consider an invariant $$I(G)$$I(G) of a graph $$G=(V,E)$$G=(V,E) defined as a summation over all edges, $$I(G) = \sum {c_{ij}x_{ij}}$$I(G)= cijxij where $$c_{ij}$$cij and $$x_{ij}$$xij is the weight and number, respectively, of edges ...