联合能耗与负载均衡的虚拟网络映射方法

为解决弹性光网络中虚拟网络映射时能耗严重、资源分配不均的问题,该文提出一种联合能耗与负载均衡的虚拟网络映射（PC-LB-VONE）方法.在虚拟节点映射时,选择相邻链路长度短、光节点计算资源多与相邻链路带宽资源多的光节点映射.在虚拟链路映射时,提出一种基于极大团的候选光路资源匹配度单路径映射策略.当单路径映射失败时,设计基于链路负载均值的多路径映射策略.仿真结果表明,所提方法能在减少弹性光网络能耗的同时均衡网络负载.     

Characterizing and decomposing classes of threshold,split, and bipartite graphs via 1-Sperner hypergraphs

A hypergraph is said to be 1-Sperner if for every two hyperedges the smallest of their two set differences is of size one. We present several applications of $1$-Sperner hypergraphs to graphs. First, we consider several ways of associating hypergraphs to graphs, namely, vertex cover, clique, independent set, dominating set, and closed neighborhood hypergraphs. For each of them, we characterize graphs yielding $1$-Sperner hypergraphs. These results give new characterizations of threshold and domishold graphs. Second, we apply a characterization of $1$-Sperner hypergraphs to derive decomposition theorems for two classes of split graphs, a class of bipartite graphs, and a class of cobipartite graphs. These decomposition theorems, based on certain matrix partitions, lead to new classes of graphs of bounded clique-width and new polynomially solvable cases of three basic domination problems: domination, total domination, and connected domination.     

On the maximum number of copies of H in graphs with given size and order

We study the maximum number $ex\left(n,e,H\right)$ of copies of a graph $H$ in graphs with a given number of vertices and edges. We show that for any fixed graph $H,ex\left(n,e,H\right)$ is asymptotically realized by the quasi‐clique provided that the edge density is sufficiently large. We also investigate a variant of this problem, when the host graph is bipartite.     

Degree sequence conditions for equal edge‐connectivity and minimum degree,depending on the clique number

Using the well‐known Theorem of Turán, we present in this paper degree sequence conditions for the equality of edge‐connectivity and minimum degree, depending on the clique number of a graph. Different examples will show that these conditions are best possible and independent of all the known results in this area. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 234–245, 2003     

Self-clique graphs and matrix permutations

The clique graph of a graph is the intersection graph of its (maximal) cliques. A graph is self-clique when it is isomorphic with its clique graph, and is clique-Helly when its cliques satisfy the Helly property. We prove that a graph is clique-Helly and self-clique if and only if it admits a quasi-symmetric clique matrix, that is, a clique matrix whose families of row and column vectors are identical. We also give a characterization of such graphs in terms of vertex-clique duality. We describe new classes of self-clique and 2-self-clique graphs. Further, we consider some problems on permuted matrices (matrices obtained by permuting the rows and/or columns of a given matrix). We prove that deciding whether a (0,1)-matrix admits a symmetric (quasi-symmetric) permuted matrix is graph (hypergraph) isomorphism complete. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 178–192, 2003     

On Standard Quadratic Optimization Problems

A standard quadratic optimization problem (QP) consists of finding (global) maximizers of a quadratic form over the standard simplex. Standard QPs arise quite naturally in copositivity-based procedures which enable an escape from local solutions. Furthermore, several important applications yield optimization problems which can be cast into a standard QP in a straightforward way. As an example, a new continuous reformulation of the maximum weight clique problem in undirected graphs is presented which considerably improves previous attacks both as numerical stability and interpretation of the results are concerned. Apparently also for the first time, an equivalence between standard QPs and QPs on the positive orthant is established. Also, a recently presented global optimization procedure (GENF - genetical engineering via negative fitness) is shortly reviewed.     

The combinatorics of pivoting for the maximum weight clique

In this paper we prove the equivalence between a pivoting-based heuristic (PBH) for the maximum weight clique problem and a combinatorial greedy heuristic. It is also proved that PBH always returns a local solution although this is not always guaranteed for Lemke's method, on which PBH is based.     

Maximal integral point sets in affine planes over finite fields

Motivated by integral point sets in the Euclidean plane, we consider integral point sets in affine planes over finite fields. An integral point set is a set of points in the affine plane over a finite field F_q, where the formally defined squared Euclidean distance of every pair of points is a square in F_q. It turns out that integral point sets over F_q can also be characterized as affine point sets determining certain prescribed directions, which gives a relation to the work of Blokhuis. Furthermore, in one important sub-case, integral point sets can be restated as cliques in Paley graphs of square order.In this article we give new results on the automorphisms of integral point sets and classify maximal integral point sets over F_q for q≤47. Furthermore, we give two series of maximal integral point sets and prove their maximality.