Maximum weight independent set of circular-arc graph and its application

In this paper, an algorithm is designed to find a maximum weight independent set of a circular-arc graph withn vertices. The weights considered here are all non-negative real numbers and associated with each of the vertex of the graph. The proposed algorithm runs in timeO(n²). Here we shown that the program slots of television channels during 24 hours can be modeled as a circular-arc graph. Each program represents a vertex and number of viewers of that program represents the weight of the corresponding vertex. Two vertices are connected by an edge iff the corresponding program slots have a common program time, i.e., ifI _i andI _j are the program slots of two programsi andj then the corresponding verticesi andj are connected by an edge iffI _i ∩ I_j 6? Φ. We also shown that the non-overlapping program slots with maximum number of viewers can be selected by computing maximum weight independent set on the corresponding circular-arc graph.     

The time constrained maximal covering salesman problem

We introduce the time constrained maximal covering salesman problem (TCMCSP) which is the generalization of the covering salesman and orienting problems. In this problem, we are given a set of vertices including a central depot, customer and facility vertices where each facility can supply the demand of some customers within its pre-determined coverage distance. Starting from the depot, the goal is to maximize the total number of covered customers by constructing a length constrained Hamiltonian cycle over a subset of facilities. We propose several mathematical programming models for the studied problem followed by a heuristic algorithm. The developed algorithm takes advantage of different procedures including swap, deletion, extraction-insertion and perturbation. Finally, an integer linear programming based improvement technique is designed to try to improve the quality of the solutions. Extensive computational experiments on a set of randomly generated instances indicate the effectiveness of the algorithm.     

On Conditional Covering Problem

The conditional covering problem (CCP) aims to locate facilities on a graph, where the vertex set represents both the demand points and the potential facility locations. The problem has a constraint that each vertex can cover only those vertices that lie within its covering radius and no vertex can cover itself. The objective of the problem is to find a set that minimizes the sum of the facility costs required to cover all the demand points. An algorithm for CCP on paths was presented by Horne and Smith (Networks 46(4):177–185, 2005). We show that their algorithm is wrong and further present a correct O(n ³) algorithm for the same. We also propose an O(n ²) algorithm for the CCP on paths when all vertices are assigned unit costs and further extend this algorithm to interval graphs without an increase in time complexity.     

A generalization of a result of Bauer and Schmeichel

We prove that if G is a 1-tough graph withn ≥ 3 vertices such thatd(u) + d(v) +d(w) ≥n+ κ —2 holds for any triple of independent verticesu, v andw ofG, thenG is hamiltonian, wherek is the vertex connectivity ofG. This generalizes a recent result of Baur and Schmeichel.     

包含随机客户的选择性旅行商问题建模及求解

针对快递配送过程中客户需求具有不确定性的特征,提出一种新的路径优化问题——包含随机客户的选择性旅行商问题,在该问题中客户每天是否具有配送需求存在一定概率,并且对客户进行配送可获取一定利润。同时考虑以上两种因素,建立该问题的数学模型, 目标为在满足行驶距离限制的条件下,找出一条经过部分客户的预优化路径,使得该路径的期望利润最大。其可用于模拟构建最后一公里快递配送的路径问题,提供更具有经济效益的配送路径。随后提出包含精细化局部搜索策略的改进遗传算法,算法根据问题特点构建初始可行解。最后通过多个计算比对结果表明,该算法具有较高的计算效率。     

Pendant-medians

The median of a network is any point in the network that minimizes the sum of the shortest distances from it to each vertex. Let's omit from this sum the distance to any vertex that is intermediate on the shortest path from the median to another vertex. In other words, include in the sum only the pendant vertices of the shortest distance spanning free. A pendant-median is any point in the network that minimizes this revised sum of the shortest distances. A pendant-median models facility locations in which customers can be served without penalty along the route to other, more distant customers.This paper presents a simple algorithm to locate a pendant-median of a tree network and presents several results for general networks.     

On the complexity of the k-customer vehicle routing problem

We investigate the complexity of the k-CUSTOMER VEHICLE ROUTING PROBLEM: Given an edge weighted graph, the problem requires to compute a minimum weight set of cyclic routes such that each contains a distinguished depot vertex and at most other k customer vertices, and every customer belongs to exactly one route.     

Independent domination in chordal graphs

A graph chordal if it does not contain any cycle of length greater than three as an induced subgraph. A set of S of vertices of a graph G = (V,E) is independent if not two vertices in S are adjacent, and is dominating if every vertex in V?S is adjacent to some vertex in S. We present a linear algorithm to locate a minimum weight independent dominating set in a chordal graph with 0–1 vertex weights.     

A Structure Theorem for Strong Immersions

A graph H is strongly immersed in G if H is obtained from G by a sequence of vertex splittings (i.e., lifting some pairs of incident edges and removing the vertex) and edge removals. Equivalently, vertices of H are mapped to distinct vertices of G (branch vertices) and edges of H are mapped to pairwise edge‐disjoint paths in G, each of them joining the branch vertices corresponding to the ends of the edge and not containing any other branch vertices. We describe the structure of graphs avoiding a fixed graph as a strong immersion. The theorem roughly states that a graph which excludes a fixed graph as a strong immersion has a tree‐like decomposition into pieces glued together on small edge cuts such that each piece of the decomposition has a path‐like linear decomposition isolating the high degree vertices.     

Finding a core of a tree with pos/neg weight

Let T?=?(V, E) be a tree. A core of T is a path P, for which the sum of the weighted distances from all vertices to this path is minimized. In this paper, we consider the semi-obnoxious case in which the vertices have positive or negative weights. We prove that, when the sum of the weights of vertices is negative, the core must be a single vertex and that, when the sum of the vertices?? weights is zero there exists a core that is a vertex. Morgan and Slater (J Algorithms 1:247?C258, 1980) presented a linear time algorithm to find the core of a tree with only positive weights of vertices. We show that their algorithm also works for semi-obnoxious problems.     

Minimal comparability completions of arbitrary graphs

A transitive orientation of an undirected graph is an assignment of directions to its edges so that these directed edges represent a transitive relation between the vertices of the graph. Not every graph has a transitive orientation, but every graph can be turned into a graph that has a transitive orientation, by adding edges. We study the problem of adding an inclusion minimal set of edges to an arbitrary graph so that the resulting graph is transitively orientable. We show that this problem can be solved in polynomial time, and we give a surprisingly simple algorithm for it. We use a vertex incremental approach in this algorithm, and we also give a more general result that describes graph classes Π for which Π completion of arbitrary graphs can be achieved through such a vertex incremental approach.     

An iterative rounding 2-approximation algorithm for the k-partial vertex cover problem

We study a generalization of the vertex cover problem. For a given graph with weights on the vertices and an integer k, we aim to find a subset of the vertices with minimum total weight, so that at least k edges in the graph are covered. The problem is called the k-partial vertex cover problem. There are some 2-approximation algorithms for the problem. In the paper we do not improve on the approximation ratios of the previous algorithms, but we derive an iterative rounding algorithm. We present our technique in two algorithms. The first is an iterative rounding algorithm and gives a （2 ＋ Q/OPT ）-approximation for the k-partial vertex cover problem where Q is the largest finite weight in the problem definition and OPT is the optimal value for the instance. The second algorithm uses the first as a subroutine and achieves an approximation ratio of 2.     

k L-list λ colouring of graphs

The k L-list λ colouring of a graph G is an L-list colouring (with positive integers) where any two colours assigned to adjacent vertices do not belong to a set λ, where the avoided assignments are listed. Moreover, the length of the list L(x), for every vertex x of G, must be less than or equal to a positive integer k, where k is the number of colours. This problem is NP-complete and we present an efficient heuristic algorithm to solve it. A fundamental aspect of the algorithm we developed is a particular technique of backtracking that permits the direct reassignment of the vertices causing the conflict if, at the moment of assigning a colour to a vertex, no colour on the list associated to it is available. An application of this algorithm to the problem of assigning arriving or leaving trains to the available tracks at a railway station is also discussed.     

Perfectly orderable graphs and almost all perfect graphs are kernelM-solvable

A graph is perfectly orderable if and only if it admits an acyclic orientation which does not contain an induced subgraph with verticesa, b, c, d and arcsab, bc, dc. Further a graph is called kernelM-solvable if for every direction of the edges (here pairs of symmetric, i.e. reversible, arcs are allowed) such that every directed triangle possesses at least two pairs of symmetric arcs, there exists a kernel, i.e. an independent setK of vertices such that every other vertex sends some arc towardsK. We prove that perfectly orderable graphs are kernelM-solvable. Using a deep result of Prömel and Steger we derive that almost all perfect graphs are kernelM-solvable.     

An analysis of the size of the minimum dominating sets in random recursive trees, using the Cockayne-Goodman-Hedetniemi algorithm

A random recursive tree on n vertices is either a single isolated vertex (for n=1) or is a vertex v_n connected to a vertex chosen uniformly at random from a random recursive tree on n−1 vertices. Such trees have been studied before [R. Smythe, H. Mahmoud, A survey of recursive trees, Theory of Probability and Mathematical Statistics 51 (1996) 1-29] as models of boolean circuits. More recently, Barabási and Albert [A. Barabási, R. Albert, Emergence of scaling in random networks, Science 286 (1999) 509-512] have used modifications of such models to model for the web and other “power-law” networks.A minimum (cardinality) dominating set in a tree can be found in linear time using the algorithm of Cockayne et al. [E. Cockayne, S. Goodman, S. Hedetniemi, A linear algorithm for the domination number of a tree, Information Processing Letters 4 (1975) 41-44]. We prove that there exists a constant d?0.3745… such that the size of a minimum dominating set in a random recursive tree on n vertices is dn+o(n) with probability approaching one as n tends to infinity. The result is obtained by analysing the algorithm of Cockayne, Goodman and Hedetniemi.     

A polynomial-time algorithm for the paired-domination problem on permutation graphs

A set S of vertices in a graph H=(V,E) with no isolated vertices is a paired-dominating set of H if every vertex of H is adjacent to at least one vertex in S and if the subgraph induced by S contains a perfect matching. Let G be a permutation graph and π be its corresponding permutation. In this paper we present an O(mn) time algorithm for finding a minimum cardinality paired-dominating set for a permutation graph G with n vertices and m edges.     

Completely unimodal numberings of a simple polytope

A completely unimodal numbering of the m vertices of a simple d-dimensional polytope is a numbering 0, 1, …,m−1 of the vertices such that on every k-dimensional face (2≤k≤d) there is exactly one local minimum (a vertex with no lower-numbered neighbors on that face). Such numberings are abstract objective functions in the sense of Adler and Saigal [1]. It is shown that a completely unimodal numbering of the vertices of a simple polytope induces a shelling of the facets of the dual simplicial polytope. The h-vector of the dual simplicial polytope is interpreted in terms of the numbering (with respect to using a local-improvement algorithm to locate the vertex numbered 0). In the case that the polytope is combinatorially equivalent to a d-dimensional cube, a ‘successor-tuple’ for each vertex is defined which carries the crucial information of the numbering for local-improvement algorithms. Combinatorial properties of these d-tuples are studied. Finally the running time of one particular local-improvement algorithm, the Random Algorithm, is studied for completely unimodal numberings of the d-cube. It is shown that for a certain class of numberings (which includes the example of Klee and Minty [8] showing that the simplex algorithm is not polynomial and all Hamiltonian saddle-free injective pseudo-Boolean functions [6]) this algorithm has expected running time that is at worst quadratic in the dimension d.     

A linear algorithm for the domination number of a series-parallel graph

A vertex u in an undirected graph G = (V, E) is said to dominate all its adjacent vertices and itself. A subset D of V is a dominating set in G if every vertex in G is dominated by a vertex in D, and is a minimum dominating set in G if no other dominating set in G has fewer vertices than D. The domination number of G is the cardinality of a minimum dominating set in G.The problem of determining, for a given positive integer k and an undirected graph G, whether G has a dominating set D in G satisfying ¦D¦ ≤ k, is a well-known NP-complete problem. Cockayne have presented a linear time algorithm for finding a minimum dominating set in a tree. In this paper, we will present a linear time algorithm for finding a minimum dominating set in a series-parallel graph.     

Coloring, location and domination of corona graphs

A vertex coloring of a graph G is an assignment of colors to the vertices of G so that every two adjacent vertices of G have different colors. A coloring related property of a graphs is also an assignment of colors or labels to the vertices of a graph, in which the process of labeling is done according to an extra condition. A set S of vertices of a graph G is a dominating set in G if every vertex outside of S is adjacent to at least one vertex belonging to S. A domination parameter of G is related to those structures of a graph that satisfy some domination property together with other conditions on the vertices of G. In this article we study several mathematical properties related to coloring, domination and location of corona graphs. We investigate the distance-k colorings of corona graphs. Particularly, we obtain tight bounds for the distance-2 chromatic number and distance-3 chromatic number of corona graphs, through some relationships between the distance-k chromatic number of corona graphs and the distance-k chromatic number of its factors. Moreover, we give the exact value of the distance-k chromatic number of the corona of a path and an arbitrary graph. On the other hand, we obtain bounds for the Roman dominating number and the locating–domination number of corona graphs. We give closed formulaes for the k-domination number, the distance-k domination number, the independence domination number, the domatic number and the idomatic number of corona graphs.     

Hypergraphs and abstract polygons

The notion of a graph has recently been generalized to include structures called hypergraphs which have two or more vertices per edge. A hypergraph is called 2-settled if each pair of distinct vertices is contained in at most one edge. A connected 2-settled hypergraph which has at least two edges through each vertex might be called an abstract polygon. Lemma: Every abstract polygon contains a cycle. Shephard and Coxeter have examined certain abstract polygons called regular complex polygons, each of which is denoted by a symbol p {q} r where there are p vertices on each edge and r edges through each vertex. Theorem: The girth of the non-starry regular complex polygon p {q} r is q. Thus, the number q is finally given a simple combinatoric interpretation.