The Clique Problem in Ray Intersection Graphs

Ray intersection graphs are intersection graphs of rays, or halflines, in the plane. We show that any planar graph has an even subdivision whose complement is a ray intersection graph. The construction can be done in polynomial time and implies that finding a maximum clique in a segment intersection graph is NP-hard. This solves a 21-year old open problem posed by Kratochvíl and Ne?et?il (Comment Math Univ Carolinae 31(1):85–93, 1990).     

求解最大团问题的熵正则化方法

最大团问题是组合优化的一个经典问题.在Motzkin和Straus的二次规划模型基础上,给出一种求解该问题的熵正则化算法.引进熵函数有两个目的,一是将问题的求解纳入信息论方法的框架,二是通过它的引进改善问题的凸性.几个标准考题的计算结果表明,该算法稳定有效.     

求解最大团问题的D函数正则化方法

最大团问题是一个经典的组合优化问题.在Motzkin和Straus的二次规划模型基础上,给出一种求解该问题的D函数正则化算法.通过引进D函数可以改善问题的凸性.几个标准考题的计算结果表明,该算法稳定有效.     

The Clique Numbers of Regular Graphs

 Let ω(G) be the clique number of a graph G. We prove that if G runs over the set of graphs with a fixed degree sequence d, then the values ω(G) completely cover a line segment [a,b] of positive integers. For an arbitrary graphic degree sequence d, we define min(ω,d) and max(ω,d) as follows:

Split Permutation Graphs

The class of split permutation graphs is the intersection of two important classes, the split graphs and permutation graphs. It also contains an important subclass, the threshold graphs. The class of threshold graphs enjoys many nice properties. In particular, these graphs have bounded clique-width and they are well-quasi-ordered by the induced subgraph relation. It is known that neither of these two properties is extendable to split graphs or to permutation graphs. In the present paper, we study the question of extendability of these two properties to split permutation graphs. We answer this question negatively with respect to both properties. Moreover, we conjecture that with respect to both of them the split permutation graphs constitute a critical class.     

Solving the Maximum Clique Problem with Symmetric Rank-One Non-negative Matrix Approximation

Finding complete subgraphs in a graph, that is, cliques, is a key problem and has many real-world applications, e.g., finding communities in social networks, clustering gene expression data, modeling ecological niches in food webs, and describing chemicals in a substance. The problem of finding the largest clique in a graph is a well-known difficult combinatorial optimization problem and is called the maximum clique problem. In this paper, we formulate a very convenient continuous characterization of the maximum clique problem based on the symmetric rank-one non-negative approximation of a given matrix and build a one-to-one correspondence between stationary points of our formulation and cliques of a given graph. In particular, we show that the local (resp. global) minima of the continuous problem corresponds to the maximal (resp. maximum) cliques of the given graph. We also propose a new and efficient clique finding algorithm based on our continuous formulation and test it on the DIMACS data sets to show that the new algorithm outperforms other existing algorithms based on the Motzkin–Straus formulation and can compete with a sophisticated combinatorial heuristic.     

Evolution towards the Maximum Clique

As is well known, the problem of finding a maximum clique in a graph isNP-hard. Nevertheless, NP-hard problems may have easy instances. This paperproposes a new, global optimization algorithm which tries to exploit favourabledata constellations, focussing on the continuous problem formulation: maximizea quadratic form over the standard simplex. Some general connections of thelatter problem with dynamic principles of evolutionary game theory areestablished. As an immediate consequence, one obtains a procedure whichconsists (a) of an iterative part similar to interior-path methods based on theso-called replicator dynamics; and (b) a routine to escape from inefficient,locally optimal solutions. For the special case of finding a maximum clique ina graph where the quadratic form arises from a regularization of the adjacencematrix, part (b), i.e. escaping from maximal cliques not of maximal size, isaccomplished with block pivoting methods based on (large) independent sets,i.e. cliques of the complementary graph. A simulation study is included whichindicates that the resulting procedure indeed has some merits.     

Combining Swaps and Node Weights in an Adaptive Greedy Approach for the Maximum Clique Problem

In this work, the NP-hard maximum clique problem on graphs is considered. Starting from basic greedy heuristics, modifications and improvements are proposed and combined in a two-phase heuristic procedure. In the first phase an improved greedy procedure is applied starting from each node of the graph; on the basis of the results of this phase a reduced subset of nodes is selected and an adaptive greedy algorithm is repeatedly started to build cliques around such nodes. In each restart the selection of nodes is biased by the maximal clique generated in the previous execution. Computational results are reported on the DIMACS benchmarks suite. Remarkably, the two-phase procedure successfully solves the difficult Brockington-Culberson instances, and is generally competitive with state-of-the-art much more complex heuristics.     

实现同一度序列的图的最大团数

图G中最大完全子图的阶数称为G的团效．ω(π)和γ(π)分别表示实现度序列π=(d_1,d_2,…,d_n)的图的最大团数和最小团数．Erds,Jacobson和Lehel开始考虑确定具有相同度序列π的图的可能的团数问题．他们证明了对于充分大的n,有ω(π)-γ(π)-n一2n~(2/3)．在本文中,我们首先估计了一类特殊可图序列的ω(π)之值,其次我们建立了一个估计任意可图序列π的ω(π)之值的算法．     

Clique Chromatic Numbers of Intersection Graphs

Mathematical Notes -     

Intersection Graphs and the Clique Operator

 Let P be a class of finite families of finite sets that satisfy a property P. We call ΩP the class of intersection graphs of families in P and CliqueP the class of graphs whose family of cliques is in P. We prove that a graph G is in ΩP if and only if there is a family of complete sets of G which covers all edges of G and whose dual family is in P. This result generalizes that of Gavril for circular-arc graphs and conduces those of Fulkerson-Gross, Gavril and Monma-Wei for interval graphs, chordal graphs, UV, DV and RDV graphs. Moreover, it leads to the characterization of Helly-graphs and dually chordal graphs as classes of intersection graphs. We prove that if P is closed under reductions, then CliqueP=Ω(P ^*∩H) (P ^*= Class of dual families of families in P). We find sufficient conditions for the Clique Operator, K, to map ΩP into ΩP ^*. These results generalize several known results for particular classes of intersection graphs. Furthermore, they lead to the Roberts-Spencer characterization for the image of K and the Bandelt-Prisner result on K-fixed classes. Received: August 18, 1997 Final version received: March 30, 1999     

Induced-Universal Graphs for Graphs with Bounded Maximum Degree

For a family \(\mathcal {F}\) of graphs, a graph U is induced-universal for \({\mathcal{F}}\) if every graph in \({\mathcal{F}}\) is an induced subgraph of U. We give a construction for an induced-universal graph for the family of graphs on n vertices with degree at most r, which has \(Cn^{\lfloor (r+1)/2\rfloor}\) vertices and \(Dn^{2\lfloor (r+1)/2\rfloor -1}\) edges, where C and D are constants depending only on r. This construction is nearly optimal when r is even in that such an induced-universal graph must have at least cn ^r/2 vertices for some c depending only on r.Our construction is explicit in that no probabilistic tools are needed to show that the graph exists or that a given graph is induced-universal. The construction also extends to multigraphs and directed graphs with bounded degree.     

An Optimal Algorithm to Solve the All-Pairs Shortest Paths Problem on Permutation Graphs

In this paper we present an optimal algorithm to solve the all-pairs shortest path problem on permutation graphs with n vertices and m edges which runs in O(n ²) time. Using this algorithm, the average distance of a permutation graph can also be computed in O(n ²) time.     

Finding Optimal Routings in Hamming Graphs

A routing R in a graph consists of a simple path p_uvfromu to v for each ordered pair of distinct vertices (u, v). We will call R optimal if all the paths p_uvare shortest paths and if edges of the graph occur equally often in the paths of R. In 1994, Solé gave a sufficient condition involving the automorphism group for a graph to have an optimal routing in this sense. Graphs which satisfy Solé’s condition are called orbital regular graphs. It is often difficult to determine whether or not a given graph is orbital regular. In this paper, we give a necessary and sufficient condition for a Hamming graph to be orbital regular with respect to a certain natural subgroup of automorphisms.     

Minimum Clique Partition in Unit Disk Graphs

The minimum clique partition (MCP) problem is that of partitioning the vertex set of a given graph into a minimum number of cliques. Given n points in the plane, the corresponding unit disk graph (UDG) has these points as vertices, and edges connecting points at distance at most 1. MCP in UDGs is known to be NP-hard and several constant factor approximations are known, including a recent PTAS. We present two improved approximation algorithms for MCP in UDGs with a realization: (I) A polynomial time approximation scheme (PTAS) running in time n^O(1/e2){n^{O(1/\varepsilon^2)}}. This improves on a previous PTAS with n^O(1/e4){n^{O(1/\varepsilon^4)}} running time by Pirwani and Salavatipour (arXiv:0904.2203v1, 2009). (II) A randomized quadratic-time algorithm with approximation ratio 2.16. This improves on a ratio 3 algorithm with O(n ²) running time by Cerioli et al. (Electron. Notes Discret. Math. 18:73–79, 2004).     

关于图的团符号控制数

引入了图的团符号控制的概念,给出了n阶图G的团符号控制数γks(G)的若干下限,确定了几类特殊图的团符号控制数,并提出了若干未解决的问题和猜想.