Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract Identifying certain conditions that ensure the Hamiltonicity of graphs is highly important and valuable due to the fact that determining whether a graph is Hamiltonian is an NP-complete problem.For a graph G with vertex set V(G) and edge set E(G), the first Zagreb index ( \(M_{1}\) ) and second Zagreb index ( \(M_{2}\) ) are defined as \(M_{1}(G)=\sum \limits _{v_{i}v_{j}\in E(G)}(d_{G}(v_{i})+d_{G}(v_{j}))\) and \(M_{2}(G)=\sum \limits _{v_{i}v_{j}\in E(G)}d_{G}(v_{i})d_{G}(v_{j})\) , where \(d_{G}(v_{i})\) denotes the degree of vertex \(v_{i}\in V(G)\) . The difference of Zagreb indices ( \(\Delta M\) ) of G is defined as \(\Delta M(G)=M_{2}(G)-M_{1}(G)\) .In this paper, we try to look for the relationship between structural graph theory and chemical graph theory. We obtain some sufficient conditions, with regards to \(\Delta M(G)\) , for graphs to be k-hamiltonian, traceable, k-edge-hamiltonian, k-connected, Hamilton-connected or k-path-coverable. PubDate: 2024-02-23

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract It is well-known that the classical Johnson’s Rule leads to optimal schedules on a two-stage flowshop. However, it is still unclear how Johnson’s Rule would help in approximation algorithms for scheduling an arbitrary number of parallel two-stage flowshops with the objective of minimizing the makespan. Thus within the paper, we study the problem and propose a new efficient algorithm that incorporates Johnson’s Rule applied on each individual flowshop with a carefully designed job assignment process to flowshops. The algorithm is successfully shown to have a runtime \(O(n \log n)\) and an approximation ratio 7/3, where n is the number of jobs. Compared with the recent PTAS result for the problem (Dong et al. in Eur J Oper Res 218(1):16–24, 2020), our algorithm has a larger approximation ratio, but it is more efficient in practice from the perspective of runtime. PubDate: 2024-02-23

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract We consider the non-preemptive scheduling problem on identical machines where there is a parameter B and each machine in every unit length time interval can process up to B different jobs. The goal function we consider is the makespan minimization and we develop an EPTAS for this problem. Prior to our work a PTAS was known only for the case of one machine and constant values of B, and even the case of non-constant values of B on one machine was not known to admit a PTAS. PubDate: 2024-02-22

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract The packing number of a signed graph \((G, \sigma )\) , denoted \(\rho (G, \sigma )\) , is the maximum number l of signatures \(\sigma _1, \sigma _2,\ldots , \sigma _l\) such that each \(\sigma _i\) is switching equivalent to \(\sigma \) and the sets of negative edges \(E^{-}_{\sigma _i}\) of \((G,\sigma _i)\) are pairwise disjoint. A signed graph packs if its packing number is equal to its negative girth. A reformulation of some well-known conjecture in extension of the 4-color theorem is that every antibalanced signed planar graph and every signed bipartite planar graph packs. On this class of signed planar graph the case when negative girth is 3 is equivalent to the 4-color theorem. For negative girth 4 and 5, based on the dual language of packing T-joins, a proof is claimed by B. Guenin in 2002, but never published. Based on this unpublished work, and using the language of packing T-joins, proofs for girth 6, 7, and 8 are published. We have recently provided a direct proof for girth 4 and in this work extend the technique to prove the case of girth 5. PubDate: 2024-02-12

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract Given a graph G with a terminal set \(R \subseteq V(G)\) , the Steiner tree problem (STREE) asks for a set \(S\subseteq V(G) {\setminus } R\) such that the graph induced on \(S\cup R\) is connected. A split graph is a graph which can be partitioned into a clique and an independent set. It is known that STREE is NP-complete on split graphs White et al. (Networks 15(1):109–124, 1985). To strengthen this result, we introduce convex ordering on one of the partitions (clique or independent set), and prove that STREE is polynomial-time solvable for tree-convex split graphs with convexity on clique (K), whereas STREE is NP-complete on tree-convex split graphs with convexity on independent set (I). We further strengthen our NP-complete result by establishing a dichotomy which says that for unary-tree-convex split graphs (path-convex split graphs), STREE is polynomial-time solvable, and NP-complete for binary-tree-convex split graphs (comb-convex split graphs). We also show that STREE is polynomial-time solvable for triad-convex split graphs with convexity on I, and circular-convex split graphs. Further, we show that STREE can be used as a framework for the dominating set problem (DS) on split graphs, and hence the classical complexity (P vs NPC) of STREE and DS is the same for all these subclasses of split graphs. Finally, from the parameterized perspective with solution size being the parameter, we show that the Steiner tree problem on split graphs is W[2]-hard, whereas when the parameter is treewidth, we show that the problem is fixed-parameter tractable, and if the parameter is the solution size and the maximum degree of I (d), then we show that the Steiner tree problem on split graphs has a kernel of size at most \((2d-1)k^{d-1}+k,~k= S \) . PubDate: 2024-02-12

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract We study a generalization of the classical Hamiltonian path problem, where multiple salesmen are positioned at the same depot, of which no more than k can be selected to service n destinations, with the objective to minimize the total travel distance. Distances between destinations (and the single depot) are assumed to satisfy the triangle inequality. We develop a non-trivial extension of the well-known Christofides heuristic for this problem, which achieves an approximation ratio of \(2-1/(2+k)\) with \(O(n^3)\) running time for arbitrary \(k\ge 1\) . PubDate: 2024-02-12

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract Shuffled Frog leaping algorithm (SFLA) is a multi population swarm intelligence algorithm which employs population partitioning techniques during the evolutionary stage. Methods adopted by SFLA for partitioning the population into memeplexes play a critical role in determining its ability to solve complex optimization problems. However, limited research is done in this direction. This work presents supervised machine learning based methods Spectral Partitioning (SCP), Agglomerative Partitioning (AGP) and Ward Hierarchical Partitioning (WHP) for distributing the solutions into memeplexes. The efficacy of variants of SFLA with these methods is assessed over CEC2015 Bound Constrained Single-Objective Computationally Expensive Numerical Optimisation problems. Analysis of results establishes that proposed SCP, AGP and WHP methods outperform Shuffled complex evolution (SCE) partitioning technique; Seed and distance based partitioning technique (SEED), Random partitioning (RAND) and Dynamic sub-swarm partitioning (DNS) for more than 10 functions. Time complexity of all the algorithms is comparable with each other. Statistical analysis using Wilcoxon signed rank sum test indicates that SCP, AGP and WHP perform significantly better than existing approaches for small dimensions. PubDate: 2024-02-11

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract To solve the problem of predicting water level in front of check gate under different time scales, a different time scale prediction model with a long short term memory (LSTM) neural network based on adaptive inertia weight comprehensive learning particle swarm optimization (AIW-CLPSO) is proposed. The AIW and CLPSO are adopted to improve the global optimization ability and convergence velocity of particle swarm optimization in the proposed model. The model was applied to the water level prediction in front of the Chaohu Lake check gate. The example of the water level prediction in front of the Chaohu Lake check gate shows that the proposed model predicts the trend of water level fluctuation better than LSTM with high accuracy of Nash coefficient up to 0.9851 and root mean square error up to 0.0273 m. The optimized algorithm can obtain the optimal parameters of the LSTM neural network, overcome the limitations of the traditional LSTM neural network in parameter selection and inaccurate prediction, and maintain good prediction results in the predicting water level in front of the check gate at different time scales.This study can provide important reference for water level prediction, scheduling warning, water resources scheduling decision and intelligent gate control in long distance water transfer projects. PubDate: 2024-01-28

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract The balanced traveling salesman problem (BTSP) is a variant of the traveling salesman problem, in which one seeks a tour that minimizes the difference between the largest and smallest edge costs in the tour. The BTSP, which is obviously NP-hard, was first investigated by Larusic and Punnen (Comput Oper Res 38(5):868–875, 2011). They proposed several heuristics based on the double-threshold framework, which converge to good-quality solutions though not always optimal. In this paper, we design a special-purpose branch-and-cut algorithm for exactly solving the BTSP. In contrast with the classical TSP, due to the BTSP’s objective function, the efficiency of algorithms for solving the BTSP depends heavily on determining correctly the largest and smallest edge costs in the tour. In the proposed branch-and-cut algorithm, we develop several mechanisms based on local cutting planes, edge elimination, and variable fixing to locate those edge costs more precisely. Other critical ingredients in our method are algorithms for initializing lower and upper bounds on the optimal value of the BTSP, which serve as warm starts for the branch-and-cut algorithm. Experiments on the same testbed of TSPLIB instances show that our algorithm can solve 63 out of 65 instances to proven optimality. PubDate: 2024-01-28

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract This paper proposes a novel Inventory-Location problem that integrates supplier selection decisions to design a three-echelon supply chain network, under a continuous (s,Q) inventory control policy at the warehouses. In this problem, a set of warehouses must be selected within a set of potential locations to serve several customers or demand zones, additionally involving the selection of the suppliers for fulfilling incoming orders from the located warehouses. The optimal solution must be determined while minimizing total system costs including supplier selection, transportation (i.e., suppliers-warehouses and warehouses-customers), inventory (i.e., cycle and safety stock), and warehouse location costs. A key element of the problem is the consideration of variable lead-times for the warehouses, which are dependent on the selection of the supplier that serve them, thus increasing model complexity. Accordingly, an efficient algorithm based on the Generalized Benders Decomposition is developed and implemented to solve the proposed Mixed Integer, Nonlinear, Nonconvex, Programming Model. The proposed solution approach relies on a convenient model formulation and decomposition that yields a Mixed Integer Linear master problem and a continuous, convex subproblem. A wide set of medium-sized synthetic instances are optimally solved in affordable times, denoting the efficiency and effectiveness of the proposed model along with the proposed solution approach. Significant scientific and managerial insights are provided and discussed. PubDate: 2024-01-24

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract Edge disjoint paths have a closed relationship with edge connectivity and are anticipated to garner increased attention in the study of the reliability and edge fault tolerance of a readily scalable interconnection network. Note that this interconnection network is always modeled as a connected graph G. The minimum of some of modified edge-cuts of a connected graph G, also known as the h-extra edge-connectivity of a graph G ( \(\lambda _{h}(G)\) ), is defined as the maximum number of the edge disjoint paths connecting any two disjoint connected subgraphs with h vertices in the graph G. From the perspective of edge-cut, the smallest cardinality of a collection of edges, whose removal divides the whole network into several connected subnetworks having at least h vertices, is the h-extra edge-connectivity of the underlying topological architecture of an interconnection network G. This paper demonstrates that the h-extra edge-connectivity of the pentanary n-cube ( \(\lambda _{h}(K_{5}^{n})\) ) appears a concentration behavior for around 50 percent of \(h\le \lfloor 5^{n}/2\rfloor \) as n approaches infinity. Let \(e=1\) for n is even and \(e=0\) for n is odd. It mainly concentrates on the value \([4g(\lceil \frac{n}{2}\rceil -r)-g(g-1)]5^{\lfloor \frac{n}{2}\rfloor +r}\) for \(g5^{\lfloor \frac{n}{2}\rfloor +r}-\lfloor \frac{[(g-1)^{2}+1]5^{2r+e}}{3}\rfloor \le h\le g5^{\lfloor \frac{n}{2}\rfloor +r}\) , where \(r=1, 2,\cdots , \lceil \frac{n}{2}\rceil -2\) , \(g\in \{1, 2,3,4\}\) ; \(r=\lceil \frac{n}{2}\rceil -1\) , \(g\in \{1,2\}\) . Furthermore, it is shown that the above upper bound and lower bound of h are sharp. PubDate: 2024-01-24

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract The Alon–Tarsi number was defined by Jensen and Toft (Graph coloring problems, Wiley, New York, 1995). The Alon–Tarsi number AT(G) of a graph G is the smallest integer k such that G has an orientation D with maximum outdegree \(k-1\) and the number of even circulation is not equal to that of odd circulations in D. It is known that \(\chi (G)\le \chi _l(G)\le AT(G)\) for any graph G, where \(\chi (G)\) and \(\chi _l(G)\) are the chromatic number and the list chromatic number of G. Denote by \(H_1 \square H_2\) and \(H_1\bowtie H_2\) the Cartesian product and the semi-strong product of two graphs \(H_1\) and \(H_2\) , respectively. Kaul and Mudrock (Electron J Combin 26(1):P1.3, 2019) proved that \(AT(C_{2k+1}\square P_n)=3\) . Li, Shao, Petrov and Gordeev (Eur J Combin 103697, 2023) proved that \(AT(C_n\square C_{2k})=3\) and \(AT(C_{2m+1}\square C_{2n+1})=4\) . Petrov and Gordeev (Mosc. J. Comb. Number Theory 10(4):271–279, 2022) proved that \(AT(K_n\square C_{2k})=n\) . Note that the semi-strong product is noncommutative. In this paper, we determine \(AT(P_m \bowtie P_n)\) , \(AT(C_m \bowtie C_{2n})\) , \(AT(C_m \bowtie P_n)\) and \(AT(P_m \bowtie C_{n})\) . We also prove that \(5\le AT(C_m \bowtie C_{2n+1})\le 6\) . PubDate: 2024-01-05

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract In an uncertain environment, it is important to investigate whether to postpone, abandon or immediately invest in photovoltaic (PV) projects. This paper applies a real options model to explore the optimal investment decision for investors and the government’s optimal incentive strategy in China’s distributed PV market. The uncertainties of feed-in tariffs (FIT) and investment costs are included in this study as critical factors affecting the options value of PV projects. Multiple scenarios are designed from different dimensions, including various subsidy durations, different resource areas, and distinct regulatory policies. The results show that not only the current FIT and investment cost affect the investment choice, but also the potential change trend of FIT and investment cost affect the investor’s preference. The results also reveal that appropriate FIT regulation can effectively induce investors who abandon investment to choose to delay investment, and significantly shorten the delay time. These conclusions can provide valuable insights for investors to optimize investment decisions. PubDate: 2023-11-24 DOI: 10.1007/s10878-023-01096-5

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract This paper studies the operations of a telemedicine service system consisting of independent hospitals [general hospital (GH) and telemedicine firm (TF)]. Through the healthcare alliance, the GH and the TF collaborate in capacity decisions and revenue sharing, and establish a green channel to refer patients. We adopt a two-stage game model to study a revenue sharing scheme of the telemedicine healthcare alliance. In the first-stage the game, the GH and the TF negotiate a revenue-sharing ratio to distribute the revenue of the referred patients. In the second stage game, given the profit-sharing ratio, GH makes capacity allocation decisions, and TF determines its own price to maximize its own revenue. Results show that the revenue sharing scheme can increase profits and promote collaboration between GH and TF. When a large number of mild patients arrive at the GH, the GH tends to participate in the alliance. For the TF, high prices do not always yield high profit under the comprehensive influence of the alliance. PubDate: 2023-11-24 DOI: 10.1007/s10878-023-01095-6

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract In this paper, we consider the \({{\mathcal{N}\mathcal{P}}}\) -hard problem of determining fixed-length cycles in undirected edge-weighted graphs. Two solution methods are proposed, one based on integer programming (IP) and one that uses bespoke local search operators. These methods are executed under a common algorithmic framework that seeks to partition problem instances into a series of smaller sub-problems. Large-scale empirical tests indicate that the local search algorithm is generally preferable to IP, even with short run times. However, it can still produce suboptimal solutions, even with relatively small graphs. PubDate: 2023-11-19 DOI: 10.1007/s10878-023-01091-w

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract Let G be a graph with vertex set V and a subset \(D\subseteq V\) . D is a total dominating set of G if every vertex in V is adjacent to a vertex in D. D is a restrained dominating set of G if every vertex in \(V\setminus D\) is adjacent to a vertex in D and another vertex in \(V\setminus D\) . D is a total restrained dominating set if D is both a total dominating set and a restrained dominating set. The minimum cardinality of total dominating sets (resp. restrained dominating sets, total restrained dominating sets) of G is called the total domination number (resp. restrained domination number, total restrained domination number) of G, denoted by \(\gamma _{t}(G)\) (resp. \(\gamma _{r}(G)\) , \(\gamma _{tr}(G)\) ). The MINIMUM TOTAL RESTRAINED DOMINATION (MTRD) problem for a graph G is to find a total restrained dominating set of minimum cardinality of G. The TOTAL RESTRAINED DOMINATION DECISION (TRDD) problem is the decision version of the MTRD problem. In this paper, firstly, we show that the TRDD problem is NP-complete for undirected path graphs, circle graphs, S-CB graphs and C-CB graphs, respectively, and that, for a S-CB graph or C-CB graph with n vertices, the MTRD problem cannot be approximated within a factor of \((1-\epsilon )\textrm{ln} n\) for any \(\epsilon >0\) unless \(NP\subseteq DTIME(n^{O(\textrm{loglog}n)})\) . Secondly, for a graph G, we prove that the problem of deciding whether \(\gamma _{r}(G) =\gamma _{tr}(G)\) is NP-hard even when G is restricted to planar graphs with maximum degree at most 4, and that the problem of deciding whether \(\gamma _{t}(G) =\gamma _{tr}(G)\) is NP-hard even when G is restricted to planar bipartite graphs with maximum degree at most 5. Thirdly, we show that the MTRD problem is APX-complete for bipartite graphs with maximum degree at most 4. Finally, we design a linear-time algorithm for solving the MTRD problem for generalized series–parallel graphs. PubDate: 2023-11-17 DOI: 10.1007/s10878-023-01090-x

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract Min–max spanning tree problem is a classical problem in combinatorial optimization. Its purpose is to find a spanning tree to minimize its maximum edge in a given edge weighted graph. Given a connected graph G, an edge weight vector w and a forest F, the partial inverse min–max spanning tree problem (PIMMST) is to find a new weighted vector \(w^*\) , so that F can be extended into a min–max spanning tree with respect to \(w^*\) and the gap between w and \(w^*\) is minimized. In this paper, we research PIMMST under the weighted bottleneck Hamming distance. Firstly, we study PIMMST with value of optimal tree restriction, a variant of PIMMST, and show that this problem can be solved in strongly polynomial time. Then, by characterizing the properties of the value of optimal tree, we present first algorithm for PIMMST under the weighted bottleneck Hamming distance with running time \(O( E ^2\log E )\) , where E is the edge set of G. Finally, by giving a necessary and sufficient condition to determine the feasible solution of this problem, we present a better algorithm for this problem with running time \(O( E \log E )\) . Moreover, we show that these algorithms can be generalized to solve these problems with capacitated constraint. PubDate: 2023-11-16 DOI: 10.1007/s10878-023-01093-8

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract In recent years, a dynamic coloring, named as zero forcing, of the vertices in a graph have attracted many researchers. For a given G and a vertex subset S, assigning each vertex of S black and each vertex of \(V\setminus S\) no color, if one vertex \(u\in S\) has a unique neighbor v in \(V\setminus S\) , then u forces v to color black. S is called a zero forcing set if S can be expanded to the entire vertex set V by repeating the above forcing process. S is regarded as a total forcing set if the subgraph G[S] satisfies \(\delta (G[S])\ge 1\) . The minimum cardinality of a total forcing set in G, denoted by \(F_t(G)\) , is named the total forcing number of G. For a graph G, p(G), q(G) and \(\phi (G)\) denote the number of pendant vertices, the number of vertices with degree at least 3 meanwhile having one pendant path and the cyclomatic number of G, respectively. In the paper, by means of the total forcing set of a spanning tree regarding a graph G, we verify that \(F_t(G)\le p(G)+q(G)+2\phi (G)\) . Furthermore, all graphs achieving the equality are determined. PubDate: 2023-11-16 DOI: 10.1007/s10878-023-01089-4

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract A \((k,g)\) -graph is a k-regular graph of girth \(g\) . Given \(k\ge 2\) and \(g\ge 3\) , \((k,g)\) -graphs of infinitely many orders are known to exist and the problem of finding a (k, g)-graph of the smallest possible order is known as the Cage Problem. The aim of our paper is to develop systematic (programmable) ways for lowering the orders of existing \((k,g)\) -graphs, while preserving their regularity and girth. Such methods, in analogy with the previously used excision, may have the potential for constructing smaller (k, g)-graphs from current smallest examples—record holders—some of which have not been improved in years. In addition, we consider constructions that preserve the regularity, the girth and the order of the considered graphs, but alter the graphs enough to possibly make them suitable for the application of our order decreasing methods. We include a detailed discussion of several specific parameter cases for which several non-isomorphic smallest examples are known to exist, and address the question of the distance between these non-isomorphic examples based on the number of changes required to move from one example to another. PubDate: 2023-11-16 DOI: 10.1007/s10878-023-01092-9

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract The dominated coloring (dom-coloring) of a graph G is a proper coloring such that each color class is dominated by at least one vertex. The dominated chromatic number (dom-chromatic number) of G is the minimum number of color classes among all dominated colorings of G, denoted by \(\chi _{\text {dom}}(G)\) . In this paper, we study the dominated coloring of Cartesian product, direct product, lexicographic product and strong product of some graphs. PubDate: 2023-11-10 DOI: 10.1007/s10878-023-01094-7