Search

This paper is concerned with a recursive algorithm as a preprocessing step to find the convex hull of n random points uniformly distributed in the plane. For such a set of points, it is shown that eliminating all but O (log n) of points can derive the same convex hull as the input set. Finally it will be shown that the running time of the algorithm is O (n). [ABSTRACT FROM AUTHOR]

In the minimum constraint removal (MCR), there is no feasible path to move from a starting point towards the goal, and the minimum constraints should be removed in order to find a collision-free path. It has been proved that MCR problem is NP-hard when constraints have arbitrary shapes or even they are in shape of convex polygons. However, it has a simple linear solution when constraints are lines and the problem is open for other cases yet. In this paper, using a reduction from Subset Sum problem, in three steps, we show that the problem is NP-hard for both weighted and unweighted line segments. [ABSTRACT FROM AUTHOR]

A set of mobile robots is placed at arbitrary points of an infinite line. The robots are equipped with GPS devices and they may communicate their positions on the line to a central authority. The collection contains an unknown subset of "spies", i.e., byzantine robots, which are indistinguishable from the non-faulty ones. The set of the non-faulty robots needs to rendezvous in the shortest possible time in order to perform some task, while the byzantine robots may try to delay their rendezvous for as long as possible. The problem facing a central authority is to determine trajectories for all robots so as to minimize the time until all the non-faulty robots have met. The trajectories must be determined without knowledge of which robots are faulty. Our goal is to minimize the competitive ratio between the time required to achieve the first rendezvous of the non-faulty robots and the time required for such a rendezvous to occur under the assumption that the faulty robots are known at the start. In this paper, we give rendezvous algorithms with bounded competitive ratio, where the central authority is informed only of the set of initial robot positions, without knowing which ones or how many of them are faulty. In general, regardless of the number of faults f ≤ n − 2 it can be shown that there is an algorithm with bounded competitive ratio. Further, we are able to give a rendezvous algorithm with optimal competitive ratio provided that the number f of faults is strictly less than ⌈ n / 2 ⌉. Note, however, that in general this algorithm does not give an estimate on the actual value of the competitive ratio. However, when an upper bound on the number of byzantine robots is known to the central authority, we can provide algorithms with constant competitive ratios and in some instances we are able to show that these algorithms are optimal. Moreover, in the cases where the number of faults is either f = 1 or f = 2 we are able to compute the competitive ratio of an optimal rendezvous algorithm, for a small number of robots. [ABSTRACT FROM AUTHOR]

With the advent of big data era, it is more and more acceptable that the topology of a network can reveal more than we can conceive. In this paper, we propose an algorithm to predict a winner of an election among several competitors based on the relationships of individuals in a social network. Convergence is proved and an extensive experiment is done to show the effectiveness of the algorithm. Our algorithm can also be used to identify members of different parties in a fairly reasonable manner. Furthermore, our algorithm is merely based on the topology of the network, which saves us a large amount of work from collecting voting intentions and executing data pre-processing. [ABSTRACT FROM AUTHOR]

A function f : V → { 0 , 1 , 2 , 3 } is a double Roman dominating function on a graph G = (V , E) if for every vertex v ∈ V with f (v) = 0 either there is a vertex u ∈ N G (v) with f (u) = 3 or there are distinct vertices u 1 , u 2 ∈ N G (v) with f (u 1) = f (u 2) = 2 and for every vertex v ∈ V with f (v) = 1 there is a vertex u ∈ N G (v) with f (u) > 1. The weight of a double Roman dominating function f on G is the value f (V) = ∑ v ∈ V f (v). The minimum weight of a double Roman dominating function on G is called the double Roman domination number of G. In this paper, we give an algorithm to compute the double Roman domination number of a given proper interval graph G = (V , E) in 𝒪 (| V |) time. [ABSTRACT FROM AUTHOR]

Given a graph and an independent set of , the 0-1 inverse maximum independent set problem (IMIS) is to delete as few vertices as possible such that becomes a maximum independent set of . It is known that IMIS is NP-hard even when the given independent set has a bounded size. In this paper, we present linear-time algorithms for IMIS on forests and unicyclic graphs. [ABSTRACT FROM AUTHOR]

Let be a graph with a positive integer weight for each vertex . One wishes to assign each edge of a positive integer as a color so that for any vertex and any two edges and incident to . Such an assignment is called an -edge-coloring of , and the maximum integer assigned to edges is called the span of . The -chromatic index of is the minimum span over all -edge-colorings of . In the paper, we present various upper and lower bounds on the -chromatic index, and obtain three efficient algorithms to find an -edge-coloring of a given graph. One of them finds an -edge-coloring with span smaller than twice the -chromatic index. [ABSTRACT FROM AUTHOR]

An adjacent vertex distinguishing proper edge coloring of a graph is a proper edge coloring of such that no pair of adjacent vertices meet the same set of colors. The minimum number of colors is called adjacent vertex distinguishing proper edge chromatic number of . In this paper, we present a new heuristic intelligent algorithm to calculate the adjacent vertex distinguishing proper edge chromatic number of graphs. To be exact, the algorithm establishes two objective subfunctions and a main objective function to find its optimal solutions by the conditions of adjacent vertex distinguishing proper edge coloring. Moreover, we test and analyze its feasibility, and the test results show that this algorithm can rapidly and efficiently calculate the adjacent vertex distinguishing proper edge chromatic number of graphs with fixed order, and its time complexity is less than . [ABSTRACT FROM AUTHOR]

Online and semi-online scheduling problems on a single machine with an availability constraint are considered in this paper. The machine has one unavailable interval in which jobs cannot be processed. Preemption is not allowed. Jobs arrive over time. The objective is to minimize makespan. First we discuss the online version of the problem. After giving its lower bound, we prove that Earliest Release Date (ERD) algorithm is an optimal algorithm. Then we study some semi-online problems in which the largest processing time, the total processing time, the largest release date, or the optimal makespan is known in advance. For these semi-online problems, we give their lower bounds, design semi-online algorithms and prove their competitive ratios, respectively. [ABSTRACT FROM AUTHOR]

Cournot competition model calculates profit by company's product quantity, but it does not take market share objective into consideration. It has obstacles of considering nonlinear aspects because the partial derivative equations are very hard to solve. Our algorithm both improves Cournot's model with consideration of market share ratio, and avoids the difficulty of solving several partial derivative equations directly. In our algorithm, we give a parameter a to describe a company's consideration of market share objective, formulate the competition between companies, and calculate new market share ratio using parameter a. We consider two network structures in our model: complete graph network and star graph network. For complete graph network, our calculation and numerical analysis is based on the case of 3 companies, but the result for general number of companies, n, is also discussed. We give a series of numerical results of new market share ratio after given the initial market share ratio and the parameter σ, and show that the initial market share ratio and new market share ratio are highly linear. Another important property in this network is the convergence of market share ratio when n goes to infinity. For star graph network, we give calculation for general cases and show that n = 3,4 are the only numbers of companies that have positive increase of the market share ratio of the company. [ABSTRACT FROM AUTHOR]

For a connected graph G (V , E) and a fixed integer r > 0 , a node q ∈ V r -dominates another node s ∈ V if d (q , s) ≤ r. An edge (q , s) is r -neighborhood covered by a vertex t , if d (q , t) ≤ r and d (s , t) ≤ r , i.e., both the vertices q and s are r -dominated by the vertex t. A set C r ⊆ V is known to be a r -neighborhood covering (r -NC) set of graph G if and only if one or more vertices of C r r -dominate each edge in E. Among all r -NC sets of graph G , the set with fewest cardinality is the minimum r -NC set of G and we indicate its cardinality as r -NC-number and we denote it by the symbol ρ (G , r). This is an NP-complete problem on general graphs. It is also NP-complete for chordal graphs. Here, we develop an O (n) time algorithm for computing a minimum r -NC set of permutation graphs, where n indicates the order of the set V. [ABSTRACT FROM AUTHOR]