直线簇上区间图的最小独立控制集

本文研究了在三种情况下直线上的区间图的最小独立控制集的计算问题:1．相交于一点的直线簇,2．除一条直线外,其余的直线都平行的直线簇,3．一条直线和直线上t个赋权的点,使得其最小独立控制集所覆盖的点的权和最大．本文给出了这三个问题的多项式时间算法,问题1可以在O(n)时间内求解,借助动态规划方法问题2和问题 3分别可以在O(n log n),O(n t)时间内求解．     

A (2 + )-Approximation Scheme for Minimum Domination on Circle Graphs

The main result of this paper is a (2 + )-approximation scheme for the minimum dominating set problem on circle graphs. We first present an O(n²) time 8-approximation algorithm for this problem and then extend it to an time (2 + )-approximation scheme for this problem. Here n and m are the number of vertices and the number of edges of the circle graph. We then present simple modifications to this algorithm that yield (3 + )-approximation schemes for the minimum connected and the minimum total dominating set problems on circle graphs. Keil (1993, Discrete Appl. Math.42, 51–63) shows that these problems are NP-complete for circle graphs and leaves open the problem of devising approximation algorithms for them. These are the first O(1)-approximation algorithms for domination problems on circle graphs.     

Cycles in 2-connected graphs

Let be a class of graphs on n vertices. For an integer c, let be the smallest integer such that if G is a graph in with more than edges, then G contains a cycle of length more than c. A classical result of Erdös and Gallai is that if is the class of all simple graphs on n vertices, then . The result is best possible when n-1 is divisible by c-1, in view of the graph consisting of copies of K_c all having exactly one vertex in common. Woodall improved the result by giving best possible bounds for the remaining cases when n-1 is not divisible by c-1, and conjectured that if is the class of all 2-connected simple graphs on n vertices, thenwhere , 2tc/2, is the number of edges in the graph obtained from K_c+1-t by adding n-(c+1-t) isolated vertices each joined to the same t vertices of K_c+1-t. By using a result of Woodall together with an edge-switching technique, we confirm Woodall's conjecture in this paper.     

带根2-连通3-正则平面地图计数

本文利用不可分离的3-正则有根平面地图的计数结果,间接地给出了2-连通 3-正则有根平面地图依边数和根面次的计数显式．     

基圈数为5的2-连通平图的构造

所有的2-连通平图可通过收缩2度点变换成无2度点的、基圈数不变的2-连通平图.本文给出了基圈数为5的、无2度点的所有2-连通平图.     

多复变数Bergman空间的支配集

本文利用伪双曲度量球对单位球上的Bergman空间的支配集给出完整刻画.证明方法是将Luecking在单位圆盘上的三个重要引理推广到单位球上,从而刻画单位球上的Bergman空间的支配集.     

Formulating and Solving the Minimum Dominating Cycle Problem

This paper introduces a formulation for the Minimum Dominating Cycle Problem. Additionally, a Branch and Cut algorithm, based on that formulation, is also investigated. So far, the algorithm contains no primal heuristics. However, it managed to solve to proven optimality, in acceptable CPU times, all test instances with up to 120 vertices.     

图的部分控制集问题的修正 Greedy算法

部分控制集问题是对于给定的顶点赋权图G=(V,E;c)和正整数K,寻找图G一个顶点子集T,使得在其控制下的顶点个数不小于K且T中顶点权和达到最小。本文讨论了部分控制集问题的NP-困难性;给出了该问题的一种修正Greedy近似算法,并对其近似度H(K)给出了证明。     

Efficient Parallel Algorithms for the Minimum Cost Flow Problem

In this paper, we propose efficient parallel implementations of the auction/sequential shortest path and the -relaxation algorithms for solving the linear minimum cost flow problem. In the parallel auction algorithm, several augmenting paths can be found simultaneously, each of them starting from a different node with positive surplus. Convergence results of an asynchronous version of the algorithm are also given. For the -relaxation method, there exist already parallel versions implemented on CM-5 and CM-2; our implementation is the first on a shared memory multiprocessor. We have obtained significant speedup values for the algorithms considered; it turns out that our implementations are effective and efficient.     

New Results on the Queens_n 2 Graph Coloring Problem

For the Queens_n ² graph coloring problems no chromatic numbers are available for n > 9 except where n is not a multiple of 2 or 3. In this paper we propose an exact algorithm that takes advantage of the particular structure of these graphs. The algorithm works on the independent sets of the graph rather than on the vertices to be colored. It combines branch and bound, for independent set assignment, with a clique based filtering procedure. A first experimentation of this approach provided the coloring number values ranging for n = 10 to n = 14.     

A New Efficient Heuristic for the Minimum Set Covering Problem

We solve approximately the minimum set covering problem by developing a new heuristic, which is essentially based on the flow algorithm originally developed by Ford and Fulkerson. We perform a comparative study of the performances (concerning solution qualities and execution times) of the flow algorithm as well as of the natural greedy heuristic for set covering originally studied by Johnson and Lovász.     

On the Number of k‐Dominating Independent Sets

We study the existence and the number of k‐dominating independent sets in certain graph families. While the case namely the case of maximal independent sets—which is originated from Erd?s and Moser—is widely investigated, much less is known in general. In this paper we settle the question for trees and prove that the maximum number of k‐dominating independent sets in n‐vertex graphs is between and if , moreover the maximum number of 2‐dominating independent sets in n‐vertex graphs is between and . Graph constructions containing a large number of k‐dominating independent sets are coming from product graphs, complete bipartite graphs, and finite geometries. The product graph construction is associated with the number of certain Maximum Distance Separable (MDS) codes.     

图论中独立支配集的求解问题并未解决

用反例证明了文[1]中的最大独立集算法和最小支配集算法的结论都是错误的,因而图论中独立支配集的求解问题并没有解决．     

Minimum Distance to the Complement of a Convex Set: Duality Result

The subject of this paper is to study the problem of the minimum distance to the complement of a convex set. Nirenberg has stated a duality theorem treating the minimum norm problem for a convex set. We state a duality result which presents some analogy with the Nirenberg theorem, and we apply this result to polyhedral convex sets. First, we assume that the polyhedral set is expressed as the intersection of some finite collection of m given half-spaces. We show that a global solution is determined by solving m convex programs. If the polyhedral set is expressed as the convex hull of a given finite set of extreme points, we show that a global minimum for a polyhedral norm is obtained by solving a finite number of linear programs.     

Minimum vertex‐diameter‐2‐critical graphs

We prove that the minimum number of edges in a vertex‐diameter‐2‐critical graph on n ≥ 23 vertices is (5n ? 17)/2 if n is odd, and is (5n/2) ? 7 if n is even. © 2005 Wiley Periodicals, Inc. J Graph Theory     

On the exponential cardinality of FDS for the ordered p-median problem

We study finite dominating sets (FDS) for the ordered median problem. This kind of problems allows to deal simultaneously with a large number of models. We show that there is no valid polynomial size FDS for the general multifacility version of this problem even on path networks.