|
|
- Minmax regret 1-sink location problems on dynamic flow path networks with
parametric weights-
Free pre-print version: Loading...
Rate this result:
What is this?
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 addresses the minmax regret 1-sink location problem on a dynamic flow path network with parametric weights. A dynamic flow path network consists of an undirected path with positive edge lengths, positive edge capacities, and nonnegative vertex weights. A path can be considered as a road, an edge length as the distance along the road, and a vertex weight as the number of people at the site. An edge capacity limits the number of people that can enter the edge per unit time. We consider the problem of locating a sink where all the people evacuate quickly. In our model, each weight is represented by a linear function of a common parameter t, and the decision maker who determines the sink location does not know the value of t. We formulate the problem under such uncertainty as the minmax regret problem. Given t and sink location x, the cost is the sum of arrival times at x for all the people determined by t. The regret for x under t is the gap between this cost and the optimal cost under t. The problem is to find the sink location minimizing the maximum regret over all t. For the problem, we propose an \(O(n^4 2^{\alpha (n)} \alpha (n)^2 \log n)\) time algorithm, where n is the number of vertices in the network and \(\alpha (\cdot )\) is the inverse Ackermann function. Also, for the special case in which every edge has the same capacity, we show that the complexity can be reduced to \(O(n^3 2^{\alpha (n)} \alpha (n) \log n)\) .
PubDate: 2024-08-26
- Efficient estimation of the modified Gromov–Hausdorff distance
between unweighted graphs-
Free pre-print version: Loading...
Rate this result:
What is this?
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 Gromov–Hausdorff distances measure shape difference between the objects representable as compact metric spaces, e.g. point clouds, manifolds, or graphs. Computing any Gromov–Hausdorff distance is equivalent to solving an NP-hard optimization problem, deeming the notion impractical for applications. In this paper we propose a polynomial algorithm for estimating the so-called modified Gromov–Hausdorff (mGH) distance, a relaxation of the standard Gromov–Hausdorff (GH) distance with similar topological properties. We implement the algorithm for the case of compact metric spaces induced by unweighted graphs as part of Python library scikit-tda, and demonstrate its performance on real-world and synthetic networks. The algorithm finds the mGH distances exactly on most graphs with the scale-free property. We use the computed mGH distances to successfully detect outliers in real-world social and computer networks.
PubDate: 2024-08-23
- Meta-heuristic-based hybrid deep learning model for vulnerability
detection and prevention in software system-
Free pre-print version: Loading...
Rate this result:
What is this?
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 Software vulnerabilities are flaws that may be exploited to cause loss or harm. Various automated machine-learning techniques have been developed in preceding studies to detect software vulnerabilities. This work tries to develop a technique for securing the software on the basis of their vulnerabilities that are already known, by developing a hybrid deep learning model to detect those vulnerabilities. Moreover, certain countermeasures are suggested based on the types of vulnerability to prevent the attack further. For different software projects taken as the dataset, feature fusion is done by utilizing canonical correlation analysis together with Deep Residual Network (DRN). A hybrid deep learning technique trained using AdamW-Rat Swarm Optimizer (AdamW-RSO) is designed to detect software vulnerability. Hybrid deep learning makes use of the Deep Belief Network (DBN) and Generative Adversarial Network (GAN). For every vulnerability, its location of occurrence within the software development procedures and techniques of alleviation via implementation level or design level activities are described. Thus, it helps in understanding the appearance of vulnerabilities, suggesting the use of various countermeasures during the initial phases of software design, and therefore, assures software security. Evaluating the performance of vulnerability detection by the proposed technique regarding recall, precision, and f-measure, it is found to be more effective than the existing methods.
PubDate: 2024-08-20
- The prize-collecting single machine scheduling with bounds and penalties
-
Free pre-print version: Loading...
Rate this result:
What is this?
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 study investigates the prize-collecting single machine scheduling with bounds and penalties (PC-SMS-BP). In this problem, a set of n jobs and a single machine are considered, where each job \(J_j\) has a processing time \(p_{j}\) , a profit \(\pi _{j}\) and a rejection penalty \(w_{j}\) . The upper bound on the processing number is U. The objective of this study is to find a feasible schedule that minimizes the makespan of the accepted jobs and the total rejection penalty of the rejected jobs under the condition that the number of the accepted jobs does not exceed a given threshold U while the total profit of the accepted jobs does not fall below a specified profit bound \(\varPi \) . We first demonstrate that this problem is NP-hard. Then, a pseudo-polynomial time dynamic programming algorithm and a fully polynomial time approximation scheme (FPTAS) are proposed. Finally, numerical experiments are conducted to compare the effectiveness of the two proposed algorithms.
PubDate: 2024-08-16
- On the complexity of minimum maximal acyclic matchings
-
Free pre-print version: Loading...
Rate this result:
What is this?
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 Low-Acy-Matching asks to find a maximal matching M in a given graph G of minimum cardinality such that the set of M-saturated vertices induces an acyclic subgraph in G. The decision version of Low-Acy-Matching is known to be \({\textsf{NP}}\) -complete. In this paper, we strengthen this result by proving that the decision version of Low-Acy-Matching remains \({\textsf{NP}}\) -complete for bipartite graphs with maximum degree 6 and planar perfect elimination bipartite graphs. We also show the hardness difference between Low-Acy-Matching and Max-Acy-Matching. Furthermore, we prove that, even for bipartite graphs, Low-Acy-Matching cannot be approximated within a ratio of \(n^{1-\epsilon }\) for any \(\epsilon >0\) unless \({\textsf{P}}={\textsf{NP}}\) . Finally, we establish that Low-Acy-Matching exhibits \(\textsf{APX}\) -hardness when restricted to 4-regular graphs.
PubDate: 2024-08-07
- Approximating the probabilistic p-Center problem under pressure
-
Free pre-print version: Loading...
Rate this result:
What is this?
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 Probabilistic p-Center problem under Pressure (Min P p CP) is a variant of the usual Min p-Center problem we recently introduced in the context of wildfire management. The problem is to locate p shelters minimizing the maximum distance people will have to cover in case of fire in order to reach the closest accessible shelter. The landscape is divided into zones and is modeled as an edge-weighted graph with vertices corresponding to zones and edges corresponding to direct connections between two adjacent zones. The risk associated with fire outbreaks is modeled using a finite set of fire scenarios. Each scenario corresponds to a fire outbreak on a single zone (i.e., on a vertex) with the main consequence of modifying evacuation paths in two ways. First, an evacuation path cannot pass through the vertex on fire. Second, the fact that someone close to the fire may not take rational decisions when selecting a direction to escape is modeled using new kinds of evacuation paths. In this paper, we characterize the set of feasible solutions of Min P p CP-instance. Then, we propose some approximation results for Min P p CP. These results require approximation results for two variants of the (deterministic) Min p-Center problem called Min MAC p-Center and Min Partial p-Center.
PubDate: 2024-08-07
- Models for two-dimensional bin packing problems with customer order spread
-
Free pre-print version: Loading...
Rate this result:
What is this?
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 address an extension of the classical two-dimensional bin packing (2BPP) that considers the spread of customer orders (2BPP-OS). The 2BPP-OS addresses a set of rectangular items, required from different customer orders, to be cut from a set of rectangular bins. All the items of a customer order are dispatched together to the next stage of production or distribution after its completion. The objective is to minimize the number of bins used and the spread of customer orders over the cutting process. The 2BPP-OS gains relevance in manufacturing environments that seek minimum waste solutions with satisfactory levels of customer service. We propose integer linear programming (ILP) models for variants of the 2BPP-OS that consider non-guillotine, 2-stage, restricted 3-stage, and unrestricted 3-stage patterns. We are not aware of integrated approaches for the 2BPP-OS in the literature despite its relevance in practical settings. Using a general-purpose ILP solver, the results show that the 2BPP-OS takes more computational effort to solve than the 2BPP, as it has to consider several symmetries that are often disregarded by the traditional 2BPP approaches. The solutions obtained by the proposed approaches have similar bin usage and significantly better metrics of customer satisfaction concerning the approaches that neglect the customer order spread.
PubDate: 2024-08-07
- Polynomial algorithms for sparse spanners on subcubic graphs
-
Free pre-print version: Loading...
Rate this result:
What is this?
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 connected graph and \(t \ge 1\) a (rational) constant. A t-spanner of G is a spanning subgraph of G in which the distance between any pair of vertices is at most t times its distance in G. We address two problems on spanners. The first one, known as the minimum t-spanner problem (MinS \(_t\) ), seeks in a connected graph a t-spanner with the smallest possible number of edges. In the second one, called minimum cost tree t-spanner problem (MCTS \(_t\) ), the input graph has costs assigned to its edges and seeks a t-spanner that is a tree with minimum cost. It is an optimization version of the tree t-spanner problem (TreeS \(_t\) ), a decision problem concerning the existence of a t-spanner that is a tree. MinS \(_t\) is known to be \({\textsc {NP}}\) -hard for every \(t \ge 2\) . On the other hand, TreeS \(_t\) admits a polynomial-time algorithm for \(t \le 2\) and is \({\textsc {NP}}\) -complete for \(t \ge 4\) ; but its complexity for \(t=3\) remains open. We focus on the class of subcubic graphs. First, we show that for such graphs MinS \(_3\) can be solved in polynomial time. These results yield a practical polynomial algorithm for TreeS \(_3\) that is of a combinatorial nature. We also show that MCTS \(_2\) can be solved in polynomial time. To obtain this last result, we prove a complete linear characterization of the polytope defined by the incidence vectors of the tree 2-spanners of a subcubic graph. A recent result showing that MinS \(_3\) on graphs with maximum degree at most 5 is NP-hard, together with the current result on subcubic graphs, leaves open only the complexity of MinS \(_3\) on graphs with maximum degree 4.
PubDate: 2024-08-07
- Customer churn prediction using a novel meta-classifier: an investigation
on transaction, Telecommunication and customer churn datasets-
Free pre-print version: Loading...
Rate this result:
What is this?
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 With the advancement of electronic service platforms, customers exhibit various purchasing behaviors. Given the extensive array of options and minimal exit barriers, customer migration from one digital service to another has become a common challenge for businesses. Customer churn prediction (CCP) emerges as a crucial marketing strategy aimed at estimating the likelihood of customer abandonment. In this paper, we aim to predict customer churn intentions using a novel robust meta-classifier. We utilized three distinct datasets: transaction, telecommunication, and customer churn datasets. Employing Decision Tree, Random Forest, XGBoost, AdaBoost, and Extra Trees as the five base supervised classifiers on these three datasets, we conducted cross-validation and evaluation setups separately. Additionally, we employed permutation and SelectKBest feature selection to rank the most practical features for achieving the highest accuracy. Furthermore, we utilized BayesSearchCV and GridSearchCV to discover, optimize, and tune the hyperparameters. Subsequently, we applied the refined classifiers in a funnel of a new meta-classifier for each dataset individually. The experimental results indicate that our proposed meta-classifier demonstrates superior accuracy compared to conventional classifiers and even stacking ensemble methods. The predictive outcomes serve as a valuable tool for businesses in identifying potential churners and taking proactive measures to retain customers, thereby enhancing customer retention rates and ensuring business sustainability.
PubDate: 2024-08-03
- First zagreb spectral radius of unicyclic graphs and trees
-
Free pre-print version: Loading...
Rate this result:
What is this?
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 light of the successful investigation of the adjacency matrix, a significant amount of its modification is observed employing numerous topological indices. The matrix corresponding to the well-known first Zagreb index is one of them. The entries of the first Zagreb matrix are \(d_{u_i}+d_{u_j}\) , if \(u_i\) is connected to \(u_j\) ; 0, otherwise, where \(d_{u_i}\) is degree of i-th vertex. The current work is concerned with the mathematical properties and chemical significance of the spectral radius ( \(\rho _1\) ) associated with this matrix. The lower and upper bounds of \(\rho _1\) are computed with characterizing extremal graphs for the class of unicyclic graphs and trees. The chemical connection of the first Zagreb spectral radius is established by exploring its role as a structural descriptor of molecules. The isomer discrimination ability of \(\rho _1\) is also explained.
PubDate: 2024-07-30
- Algorithms for a two-machine no-wait flow shop scheduling problem with two
competing agents-
Free pre-print version: Loading...
Rate this result:
What is this?
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 following two-machine no-wait flow shop scheduling problem with two competing agents \(F2~ ~M_1\rightarrow M_2,~ M_2,~ p_{ij}^{A} = p,~ no\text{- }wait~ ~C_{\max }^A:~ C_{\max }^B~\le Q \) : Given a set of n jobs \(\mathcal {J} = \{ J_1, J_2, \ldots , J_n\}\) and two competing agents A and B. Agent A is associated with a set of \(n_A\) jobs \(\mathcal {J}^A = \{J_1^A, J_2^A, \ldots , J_{n_A}^A\}\) to be processed on the machine \(M_1\) first and then on the machine \(M_2\) with no-wait constraint, and agent B is associated with a set of \(n_B\) jobs \(\mathcal {J}^B = \{J_1^B, J_2^B, \ldots , J_{n_B}^B\}\) to be processed on the machine \(M_2\) only, where the processing times for the jobs of agent A are all the same (i.e., \(p_{ij}^A = p\) ), \(\mathcal {J} = \mathcal {J}^A \cup \mathcal {J}^B\) and \(n = n_A + n_B\) . The objective is to build a schedule \(\pi \) of the n jobs that minimizing the makespan of agent A while maintaining the makespan of agent B not greater than a given value Q. We first show that the problem is polynomial time solvable in some special cases. For the non-solvable case, we present an \(O(n \log n)\) -time \((1 + \frac{1}{n_A +1})\) -approximation algorithm and show that this ratio of \((1 + \frac{1}{n_A +1})\) is asymptotically tight. Finally, \((1+\epsilon )\) -approximation algorithms are provided.
PubDate: 2024-07-30
- An improved upper bound for the online graph exploration problem on
unicyclic graphs-
Free pre-print version: Loading...
Rate this result:
What is this?
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 online graph exploration problem, which was proposed by Kalyanasundaram and Pruhs (Theor Comput Sci 130(1):125–138, 1994), is defined as follows: Given an edge-weighted undirected connected graph and a specified vertex (called the origin), the task of an algorithm is to compute a path from the origin to the origin which contains all the vertices of the given graph. The goal of the problem is to find such a path of minimum weight. At each time, an online algorithm knows only the weights of edges each of which consists of visited vertices or vertices adjacent to visited vertices. Fritsch (Inform Process Lett 168:1006096, 2021) showed that the competitive ratio of an online algorithm is at most three for any unicyclic graph. On the other hand, Brandt et al. (Theor Comput Sci 839:176–185, 2020) showed a lower bound of two on the competitive ratio for any unicyclic graph. In this paper, we showed the competitive ratio of an online algorithm is at most 5/2 for any unicyclic graph.
PubDate: 2024-07-29
- Maximizing stochastic set function under a matroid constraint from
decomposition-
Free pre-print version: Loading...
Rate this result:
What is this?
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 work, we focus on maximizing the stochastic DS decomposition problem. If the constraint is a uniform matroid, we design an adaptive policy, namely Myopic Parameter Conditioned Greedy, and prove its theoretical guarantee \(f(\varTheta (\pi _k))-(1-c_G)g(\varTheta (\pi _k))\ge (1-e^{-1})F(\pi ^*_A, \varTheta (\pi _k)) - G(\pi ^*_A,\varTheta (\pi _k))\) , where \(F(\pi ^*_A, \varTheta (\pi _k)) = \mathbb {E}_{\varTheta }[f(\varTheta (\pi ^*_A)) \vert \varTheta (\pi _k)]\) . When the constraint is a general matroid constraint, we design the Parameter Measured Continuous Conditioned Greedy to return a fractional solution. To round an integer solution from the fractional solution, we adopt the lattice contention resolution and prove that there is a \((b, \frac{1-e^{-b}}{b})\) lattice CR scheme under a matroid constraint. Additionally, we adopt the pipage rounding to obtain a non-adaptive policy with the theoretical guarantee \(F(\pi )-(1-c_G)G(\pi ) \ge (1-e^{-1}) F(\pi ^*_A) - G(\pi ^*_A) - O(\epsilon )\) and utlize the \((1,1-e^{-1})\) -lattice contention resolution scheme \(\tau \) to obtain an adaptive solution \(\mathbb {E}_{\tau \sim \varLambda } [f(\tau (\varTheta (\pi )))- (1-c_G) g(\tau (\varTheta (\pi )))] \ge (1-e^{-1})^2F(\pi ^*_A,\varTheta (\pi )) - (1-e^{-1}) G(\pi ^*_A,\varTheta (\pi )) -O(\epsilon )\) . Since any set function can be expressed as the DS decomposition, our framework provides a method for solving the maximization problem of set functions defined on a random variable set.
PubDate: 2024-07-28
- Risk-adjusted exponential gradient strategies for online portfolio
selection-
Free pre-print version: Loading...
Rate this result:
What is this?
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 concerns online portfolio selection problem whose main feature is with no any statistical assumption on future asset prices. Since online portfolio selection aims to maximize the cumulative wealth, most existing online portfolio strategies do not consider risk factors into the model. To enrich the research on online portfolio selection, we introduce the risk factors into the model and propose two novel risk-adjusted online portfolio strategies. More specifically, we first choose several exponential gradient ( \(\text {EG}(\eta )\) ) with different values of parameter \(\eta \) to build an expert pool. Later, we construct two risk methods to measure performance of each expert. Finally, we calculate the portfolio by the weighted average over all expert advice. We present theoretical and experimental results respectively to analyze the performance of the proposed strategies. Theoretical results show that the proposed strategies not only track the expert with the lowest risk, but also are universal, i.e., they exhibit the same asymptotic average logarithmic growth rate as best constant rebalanced portfolio (BCRP) determined in hindsight. We conduct extensive experiments by using daily stock data collected from the American and Chinese stock markets. Experimental results show the proposed strategies outperform existing online portfolio in terms of the return and risk metrics in most cases.
PubDate: 2024-07-28
- Embedding and the first Laplace eigenvalue of a finite graph
-
Free pre-print version: Loading...
Rate this result:
What is this?
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 Göring–Helmberg–Wappler introduced optimization problems regarding embeddings of a graph into a Euclidean space and the first nonzero eigenvalue of the Laplacian of a graph, which are dual to each other in the framework of semidefinite programming. In this paper, we introduce a new graph-embedding optimization problem, and discuss its relation to Göring–Helmberg–Wappler’s problems. We also identify the dual problem to our embedding optimization problem. We solve the optimization problems for distance-regular graphs and the one-skeleton graphs of the \(\textrm{C}_{60}\) fullerene and some other Archimedian solids.
PubDate: 2024-07-16
- Improved kernelization and fixed-parameter algorithms for bicluster
editing-
Free pre-print version: Loading...
Rate this result:
What is this?
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 bipartite graph G, the Bicluster Editing problem asks for the minimum number of edges to insert or delete in G so that every connected component is a bicluster, i.e. a complete bipartite graph. This has several applications, including in bioinformatics and social network analysis. In this work, we study the parameterized complexity under the natural parameter k, which is the number of allowed modified edges. We first show that one can obtain a kernel with 4.5k vertices, an improvement over the previously known quadratic kernel. We then propose an algorithm that runs in time \(O^*(2.581^k)\) . Our algorithm has the advantage of being conceptually simple and should be easy to implement.
PubDate: 2024-07-03
- Finding a second Hamiltonian decomposition of a 4-regular multigraph by
integer linear programming-
Free pre-print version: Loading...
Rate this result:
What is this?
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 Hamiltonian decomposition of a regular graph is a partition of its edge set into Hamiltonian cycles. We consider the second Hamiltonian decomposition problem: for a 4-regular multigraph, find 2 edge-disjoint Hamiltonian cycles different from the given ones. This problem arises in polyhedral combinatorics as a sufficient condition for non-adjacency in the 1-skeleton of the traveling salesperson polytope. We introduce two integer linear programming models for the problem based on the classical Dantzig-Fulkerson-Johnson and Miller-Tucker-Zemlin formulations for the traveling salesperson problem. To enhance the performance on feasible problems, we supplement the algorithm with a variable neighborhood descent heuristic w.r.t. two neighborhood structures and a chain edge fixing procedure. Based on the computational experiments, the Dantzig-Fulkerson-Johnson formulation showed the best results on directed multigraphs, while on undirected multigraphs, the variable neighborhood descent heuristic was especially effective.
PubDate: 2024-07-03
- A hybrid grey wolf optimizer for engineering design problems
-
Free pre-print version: Loading...
Rate this result:
What is this?
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 Grey wolf optimizer (GWO) is one of the most popular metaheuristics, and it has been presented as highly competitive with other comparison methods. However, the basic GWO needs some improvement, such as premature convergence and imbalance between exploitation and exploration. To address these weaknesses, this paper develops a hybrid grey wolf optimizer (HGWO), which combines the Halton sequence, dimension learning-based, crisscross strategy, and Cauchy mutation strategy. Firstly, the Halton sequence is used to enlarge the search scope and improve the diversity of the solutions. Then, the dimension learning-based is used for position update to balance exploitation and exploration. Furthermore, the crisscross strategy is introduced to enhance convergence precision. Finally, the Cauchy mutation strategy is adapted to avoid falling into the local optimum. The effectiveness of HGWO is demonstrated by comparing it with advanced algorithms on the 15 benchmark functions in different dimensions. The results illustrate that HGWO outperforms other advanced algorithms. Moreover, HGWO is used to solve eight real-world engineering problems, and the results demonstrate that HGWO is superior to different advanced algorithms.
PubDate: 2024-07-03
- Injective edge-coloring of claw-free subcubic graphs
-
Free pre-print version: Loading...
Rate this result:
What is this?
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 An injective edge-coloring of a graph G is an edge-coloring of G such that any two edges that are at distance 2 or in a common triangle receive distinct colors. The injective chromatic index of G is the minimum number of colors needed to guarantee that G admits an injective edge-coloring. Ferdjallah, Kerdjoudj and Raspaud showed that the injective chromatic index of every subcubic graph is at most 8, and conjectured that 8 can be improved to 6. Kostochka, Raspaud and Xu further proved that every subcubic graph has the injective chromatic index at most 7, and every subcubic planar graph has the injective chromatic index at most 6. In this paper, we consider the injective edge-coloring of claw-free subcubic graphs. We show that every connected claw-free subcubic graph, apart from two exceptions, has the injective chromatic index at most 5. We also consider the list version of injective edge-coloring and prove that the list injective chromatic index of every claw-free subcubic graph is at most 6. Both results are sharp and strengthen a recent result of Yang and Wu which asserts that every claw-free subcubic graph has the injective chromatic index at most 6.
PubDate: 2024-07-03
- Approximation algorithms for two clustered arc routing problems
-
Free pre-print version: Loading...
Rate this result:
What is this?
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 strongly connected mixed graph \(G=(V,E,A)\) , where V represents the vertex set, E is the undirected edge set, and A is the directed arc set, \(R \subseteq E\) is a subset of required edges and is divided into p clusters \(R_1,R_2,\dots ,R_p\) , and A is a set of required arcs and is partitioned into q clusters \(A_1,A_2,\ldots ,A_q\) . Each edge in E and each arc in A are associated with a nonnegative weight and the weight function satisfies the triangle inequality. In this paper we consider two clustered arc routing problems. The first is the Clustered Rural Postman Problem, in which A is empty and the objective is to find a minimum-weight closed walk such that all the edges in R are serviced and the edges in \(R_i\) ( \(1\le i \le p\) ) are serviced consecutively. The other is the Clustered Stacker Crane Problem, in which R is empty and the goal is to find a minimum-weight closed walk that traverses all the arcs in A and services the arcs in \(A_j\) ( \(1\le j \le q\) ) consecutively. For both problems, we propose constant-factor approximation algorithms with ratios 13/6 and 19/6, respectively.
PubDate: 2024-07-03
|
Hybrid journal (It can contain Open Access articles)
