Optimal RSUs deployment with delay bound along highways in VANET

In order to broadcast an alert message from the accident site to the control center as soon as possible, the roadside units (RSUs) act as the critical component in vehicular ad hoc networks (VANETs). It is not possible to make a pervasive RSU deployment due to the huge cost and market requirement. Hence, how to deploy a minimum number of RSUs in a given region becomes a challenge problem. In this paper, we present an analysis for the total delay of broadcasting alert messages in VANETs along highways. Based on the analysis, the relationship between optimal number of RSUs with the highway distance is given. Moreover, the experiment results verifies the delay analysis and the optimization of RSUs deployment.     

Minimizing the number of tardy jobs in two-machine settings with common due date

We consider two-machine scheduling problems with job selection. We analyze first the two-machine open shop problem and provide a best possible linear time algorithm. Then, a best possible linear time algorithm is derived for the job selection problem on two unrelated parallel machines. We also show that an exact approach can be derived for both problems with complexity \(O(p(n) \times \sqrt{2}^n)\), p being a polynomial function of n.     

Parameterized algorithms for min–max 2-cluster editing

For a given graph and an integer t, the Min–Max 2-Clustering problem asks if there exists a modification of a given graph into two maximal disjoint cliques by inserting or deleting edges such that the number of the editing edges incident to each vertex is at most t. It has been shown that the problem can be solved in polynomial time for \(t<n/4\), where n is the number of vertices. In this paper, we design parameterized algorithms for different ranges of t. Let \(k=t-n/4\). We show that the problem is polynomial-time solvable when roughly \(k<\sqrt{n/32}\). When \(k\in o(n)\), we design a randomized and a deterministic algorithm with sub-exponential time parameterized complexity, i.e., the problem is in SUBEPT. We also show that the problem can be solved in \(O({2}^{n/r}\cdot n^2)\) time for \(k<n/12\) and in \(O(n^2\cdot 2^{3n/4+k})\) time for \(n/12\le k< n/4\), where \(r=2+\lfloor (n/4-3k-2)/(2k+1) \rfloor \ge 2\).     

Characterizations of <Emphasis Type="Italic">k</Emphasis>-cutwidth critical trees

The cutwidth problem for a graph G is to embed G into a path such that the maximum number of overlap edges (i.e., the congestion) is minimized. The investigations of critical graphs and their structures are meaningful in the study of a graph-theoretic parameters. We study the structures of k-cutwidth \((k>1)\) critical trees, and use them to characterize the set of all 4-cutwidth critical trees.     

Improved upper bound for the degenerate and star chromatic numbers of graphs

Let \(G=G(V,E)\) be a graph. A proper coloring of G is a function \(f:V\rightarrow N\) such that \(f(x)\ne f(y)\) for every edge \(xy\in E\). A proper coloring of a graph G such that for every \(k\ge 1\), the union of any k color classes induces a \((k-1)\)-degenerate subgraph is called a degenerate coloring; a proper coloring of a graph with no two-colored \(P_{4}\) is called a star coloring. If a coloring is both degenerate and star, then we call it a degenerate star coloring of graph. The corresponding chromatic number is denoted as \(\chi _{sd}(G)\). In this paper, we employ entropy compression method to obtain a new upper bound \(\chi _{sd}(G)\le \lceil \frac{19}{6}\Delta ^{\frac{3}{2}}+5\Delta \rceil \) for general graph G.     

Total edge irregularity strength of accordion graphs

An edge irregular total k-labeling \(\varphi : V\cup E \rightarrow \{ 1,2, \dots , k \}\) of a graph \(G=(V,E)\) is a labeling of vertices and edges of G in such a way that for any different edges xy and \(x'y'\) their weights \(\varphi (x)+ \varphi (xy) + \varphi (y)\) and \(\varphi (x')+ \varphi (x'y') + \varphi (y')\) are distinct. The total edge irregularity strength, tes(G), is defined as the minimum k for which G has an edge irregular total k-labeling. We have determined the exact value of the total edge irregularity strength of accordion graphs.     

Distance domination in graphs with given minimum and maximum degree

For an integer \(k \ge 1\), a distance k-dominating set of a connected graph G is a set S of vertices of G such that every vertex of V(G) is at distance at most k from some vertex of S. The distance k-domination number \(\gamma _k(G)\) of G is the minimum cardinality of a distance k-dominating set of G. In this paper, we establish an upper bound on the distance k-domination number of a graph in terms of its order, minimum degree and maximum degree. We prove that for \(k \ge 2\), if G is a connected graph with minimum degree \(\delta \ge 2\) and maximum degree \(\Delta \) and of order \(n \ge \Delta + k - 1\), then \(\gamma _k(G) \le \frac{n + \delta - \Delta }{\delta + k - 1}\). This result improves existing known results.     

Is there any polynomial upper bound for the universal labeling of graphs?

A universal labeling of a graph G is a labeling of the edge set in G such that in every orientation \(\ell \) of G for every two adjacent vertices v and u, the sum of incoming edges of v and u in the oriented graph are different from each other. The universal labeling number of a graph G is the minimum number k such that G has universal labeling from \(\{1,2,\ldots , k\}\) denoted it by \(\overrightarrow{\chi _{u}}(G) \). We have \(2\Delta (G)-2 \le \overrightarrow{\chi _{u}} (G)\le 2^{\Delta (G)}\), where \(\Delta (G)\) denotes the maximum degree of G. In this work, we offer a provocative question that is: “Is there any polynomial function f such that for every graph G, \(\overrightarrow{\chi _{u}} (G)\le f(\Delta (G))\)?”. Towards this question, we introduce some lower and upper bounds on their parameter of interest. Also, we prove that for every tree T, \(\overrightarrow{\chi _{u}}(T)={\mathcal {O}}(\Delta ^3) \). Next, we show that for a given 3-regular graph G, the universal labeling number of G is 4 if and only if G belongs to Class 1. Therefore, for a given 3-regular graph G, it is an \( {{\mathbf {N}}}{{\mathbf {P}}} \)-complete to determine whether the universal labeling number of G is 4. Finally, using probabilistic methods, we almost confirm a weaker version of the problem.     

The Weight Function Lemma for graph pebbling

Graph pebbling is a network model for studying whether or not a given supply of discrete pebbles can satisfy a given demand via pebbling moves. A pebbling move across an edge of a graph takes two pebbles from one endpoint and places one pebble at the other endpoint; the other pebble is lost in transit as a toll. It has been shown that deciding whether a supply can meet a demand on a graph is NP-complete. The pebbling number of a graph is the smallest t such that every supply of t pebbles can satisfy every demand of one pebble byt a vertex. Deciding if the pebbling number is at most k is \(\Pi _2^\mathsf{P}\)-complete. In this paper we develop a tool, called the Weight Function Lemma, for computing upper bounds and sometimes exact values for pebbling numbers with the assistance of linear optimization. With this tool we are able to calculate the pebbling numbers of much larger graphs than in previous algorithms, and much more quickly as well. We also obtain results for many families of graphs, in many cases by hand, with much simpler and remarkably shorter proofs than given in previously existing arguments (certificates typically of size at most the number of vertices times the maximum degree), especially for highly symmetric graphs. Here we apply the Weight Function Lemma to several specific graphs, including the Petersen, Lemke, \(4\mathrm{th}\) weak Bruhat, and Lemke squared, as well as to a number of infinite families of graphs, such as trees, cycles, graph powers of cycles, cubes, and some generalized Petersen and Coxeter graphs. In doing so we partly answer a question of Pachter, et al., by computing the pebbling exponent of cycles to within an asymptotically small range. It is conceivable that this method yields an approximation algorithm for graph pebbling.     

Fibonacci helps to evacuate from a convex region in a grid network

This study considers an evacuation problem where the evacuees try to escape to the boundary of an affected area, which is convex, and a grid network is embedded in the area. The boundary is unknown to the evacuees and we propose an online evacuation strategy based on the Fibonacci sequence. This strategy is proved to have a competitive ratio of 19.5, which is better than the best previously reported result of 21.