Four problems on graphs with excluded minors

The four problems we consider are the Chinese postman, odd cut, co-postman, and odd circuit problems. Seymour's characterization of matroids having the max-flow min-cut property can be specialized to each of these four problems to show that the property holds whenever the graph has no certain excluded minor. We develop a framework for characterizing graphs not having these excluded minors and use the excluded minor characterizations to solve each of the four optimization problems. In this way, a constructive proof of Seymour's theorem is given for these special cases. We also show how to solve the Chinese postman problem on graphs having no four-wheel minor, where the max-flow min-cut property need not hold.     

基于Hamilton路模型的蛋白质结构预测的研究

提出一种基于Hamilton路模型的新方法研究蛋白质结构预测问题,为使结构匹配序列,把已知蛋白质的3D结构信息转化为一个加权的完全图Kn,则求这个特定空间结构所匹配的氨基酸残基序列问题转化为求Kn图的最小H路问题.用此方法研究了72个单链蛋白质结构,结果表明Kn图的最小H路对应此蛋白质的序列,图的顶点数n与最小H路总长度成正比.     

Fuzzy graphs modelling for HazMat telegeomonitoring

Telegeomonitoring system development combines two heterogeneous technologies: the geographical information systems technology (GIS) and telecommunications technology. In this paper, we give the system components for telegeomonitoring transportation of hazardous materials. The telegeomonitoring system uses GIS to capture civil infrastructure (urban network, land use, industries, etc.) and decision support systems technology to allow risks analysis and evaluate routing strategies that minimize transportation risk. Routing algorithms are to this effect adapted to graphs of the fuzzy risk. A new algebraic structure is proposed to solve a path-finding problem in a fuzzy graph. This algebraic structure is adapted precisely to solve the problem of the K-best fuzzy shortest paths. The approach that we proposed, consists of defining generic structures of operator’s traversal problem in fuzzy graphs. The principal contribution of our approach is to build adequate structures of path algebra to solve the problem of graph traversal in a fuzzy graph without negative circuits. Foundations of the system studied in this work will be able to be transposed to other fields of transportation.     

Spectral methods for graph clustering - A survey

Graph clustering is an area in cluster analysis that looks for groups of related vertices in a graph. Due to its large applicability, several graph clustering algorithms have been proposed in the last years. A particular class of graph clustering algorithms is known as spectral clustering algorithms. These algorithms are mostly based on the eigen-decomposition of Laplacian matrices of either weighted or unweighted graphs. This survey presents different graph clustering formulations, most of which based on graph cut and partitioning problems, and describes the main spectral clustering algorithms found in literature that solve these problems.     

Generating facets for the cut polytope of a graph by triangular elimination

The cut polytope of a graph arises in many fields. Although much is known about facets of the cut polytope of the complete graph, very little is known for general graphs. The study of Bell inequalities in quantum information science requires knowledge of the facets of the cut polytope of the complete bipartite graph or, more generally, the complete k-partite graph. Lifting is a central tool to prove certain inequalities are facet inducing for the cut polytope. In this paper we introduce a lifting operation, named triangular elimination, applicable to the cut polytope of a wide range of graphs. Triangular elimination is a specific combination of zero-lifting and Fourier–Motzkin elimination using the triangle inequality. We prove sufficient conditions for the triangular elimination of facet inducing inequalities to be facet inducing. The proof is based on a variation of the lifting lemma adapted to general graphs. The result can be used to derive facet inducing inequalities of the cut polytope of various graphs from those of the complete graph. We also investigate the symmetry of facet inducing inequalities of the cut polytope of the complete bipartite graph derived by triangular elimination.      

应用图论分析与最优化理论来数据挖掘大规模水牛普里昂蛋白结构数据

图论、最优化理论显然在蛋白质结构的研究中大有用场. 首先, 调查/回顾了研究蛋白质结构的所有图论模型. 其后, 建立了一个图论模型: 让蛋白质的侧链来作为图的顶点, 应用图论的诸如团、 $k$-团、 社群、 枢纽、聚类等概念来建立图的边. 然后, 应用数学最优化的现代摩登数据挖掘算法/方法来分析水牛普里昂蛋白结构的大数据. 成功与令人耳目一新的数值结果将展示给朋友们.     

Positive Semidefinite Rank-Based Correlation Matrix Estimation With Application to Semiparametric Graph Estimation

Many statistical methods gain robustness and flexibility by sacrificing convenient computational structures. In this article, we illustrate this fundamental tradeoff by studying a semiparametric graph estimation problem in high dimensions. We explain how novel computational techniques help to solve this type of problem. In particular, we propose a nonparanormal neighborhood pursuit algorithm to estimate high-dimensional semiparametric graphical models with theoretical guarantees. Moreover, we provide an alternative view to analyze the tradeoff between computational efficiency and statistical error under a smoothing optimization framework. Though this article focuses on the problem of graph estimation, the proposed methodology is widely applicable to other problems with similar structures. We also report thorough experimental results on text, stock, and genomic datasets.     

Column generation and sequential heuristic procedure for solving an irregular shape cutting stock problem

The research addressing two-dimensional (2D) irregular shape packing has largely focused on the strip packing variant of the problem. However, it can be argued that this is a simplification. The materials from which pieces are required to be cut will ultimately have a fixed length either due to the physical dimensions of the material or through constraints on the cutting machinery. Hence, in order to cut all the pieces, multiple sheets may be required. From this scenario arises the 2D irregular shape cutting stock problem. In this paper, we will present implementations of cutting stock approaches adapted to handle irregular shapes, including two approaches based on column generation (CG) and a sequential heuristic procedure. In many applications, setup costs can be reduced if the same pattern layout is cut from multiple sheets; hence there is a trade-off between material waste and number of patterns. Therefore, we describe the formulation and implementation of an adaptation of the CG method to control the number of different patterns. CG is a common method for the cutting stock problem; however, when the pieces are irregular the sub-problem cannot be solved optimally. Hence we implement CG and solve the sub-problem using the beam search heuristic. Further, we introduce a version of CG for instances where the number of rows is less than the number of columns.     

On the max‐cut of sparse random graphs

We consider the problem of estimating the size of a maximum cut (Max‐Cut problem) in a random Erdős‐Rényi graph on n nodes and edges. It is shown in Coppersmith et al. that the size of the maximum cut in this graph normalized by the number of nodes belongs to the asymptotic region with high probability (w.h.p.) as n increases, for all sufficiently large c. The upper bound was obtained by application of the first moment method, and the lower bound was obtained by constructing algorithmically a cut which achieves the stated lower bound. In this paper, we improve both upper and lower bounds by introducing a novel bounding technique. Specifically, we establish that the size of the maximum cut normalized by the number of nodes belongs to the interval w.h.p. as n increases, for all sufficiently large c. Instead of considering the expected number of cuts achieving a particular value as is done in the application of the first moment method, we observe that every maximum size cut satisfies a certain local optimality property, and we compute the expected number of cuts with a given value satisfying this local optimality property. Estimating this expectation amounts to solving a rather involved two dimensional large deviations problem. We solve this underlying large deviation problem asymptotically as c increases and use it to obtain an improved upper bound on the Max‐Cut value. The lower bound is obtained by application of the second moment method, coupled with the same local optimality constraint, and is shown to work up to the stated lower bound value . It is worth noting that both bounds are stronger than the ones obtained by standard first and second moment methods. Finally, we also obtain an improved lower bound of on the Max‐Cut for the random cubic graph or any cubic graph with large girth, improving the previous best bound of .     

周长为3的m限制边割连通图

如果连通图的G存在边割S,使得G-S的每一个连通分支都含有至少m个顶点,则称图G是m限制边连通的.本文刻画了周长为3的m限制边连通图.     

A branch and cut algorithm for the hierarchical network design problem

The Hierarchical Network Design Problem consists of locating a minimum cost bi-level network on a graph. The higher level sub-network is a path visiting two or more nodes. The lower level sub-network is a forest connecting the remaining nodes to the path. We optimally solve the problem using an ad hoc branch and cut procedure. Relaxed versions of a base model are solved using an optimization package and, if binary variables have fractional values or if some of the relaxed constraints are violated in the solution, cutting planes are added. Once no more cuts can be added, branch and bound is used. The method for finding valid cutting planes is presented. Finally, we use different available test instances to compare the procedure with the best known published optimal procedure, with good results. In none of the instances we needed to apply branch and bound, but only the cutting planes.     

A note on packing paths in planar graphs

Seymour (1981) proved that the cut criterion is necessary and sufficient for the solvability of the edge-disjoint paths problem when the union of the supply graph and the demand graph is planar and Eulerian. When only planarity is required, Middendorf and Pfeiffer (1993) proved the problem to be NP-complete. For this case, Korach and Penn (1992) proved that the cut criterion is sufficient for the existence of a near-complete packing of paths. Here we generalize this result by showing how a natural strengthening of the cut criterion yields better packings of paths.Analogously to Seymour's approach, we actually prove a theorem on packing cuts in an arbitrary graph and then the planar edge-disjoint paths case is obtained by planar dualization. The main result is derived from a theorem of Seb (1990) on the structure of ±1 weightings of a bipartite graph with no negative circuits.Research partially supported by the Hungarian National Foundation for Scientific Research Grants OTKA 2118 and 4271.     

The 1-Laplacian Cheeger Cut: Theory and Algorithms

This paper presents a detailed review of both theory and algorithms for the Cheeger cut based on the graph 1-Laplacian. In virtue of the cell structure of the feasible set, we propose a cell descend (CD) framework for achieving the Cheeger cut. While plugging the relaxation to guarantee the decrease of the objective value in the feasible set, from which both the inverse power (IP) method and the steepest descent (SD) method can also be recovered, we are able to get two specified CD methods. Comparisons of all these methods are conducted on several typical graphs.     

Permanents of graphs with cut vertices

In this article, we determine upper bounds for the permanent of the adjacency matrix of a graph with cut vertices in terms of the order of the graph and the number of its cut vertices.     

Permanents of graphs with cut vertices

In this article, we determine upper bounds for the permanent of the adjacency matrix of a graph with cut vertices in terms of the order of the graph and the number of its cut vertices.     

关于超欧拉图的一个注记

设G是无向无环的有限图 ,若G有一个生成子图是欧拉图 (Euler) ,则称G是超欧拉图 (Supereulerian) .本文不利用收缩方法 ,直接证明了 :当图G至多差一边有两棵边不相交的生成树时 ,G是超欧拉图或者G有割边 .     

Minimizing breaks by maximizing cuts

We propose to solve the break minimization problem in sports scheduling by transforming it into a maximum cut problem in an undirected graph and applying a branch-and-cut algorithm. Our approach outperforms previous approaches with constraint programming and integer programming techniques.     

The least eigenvalue of a graph with cut vertices

In this paper we characterize the unique graph whose least eigenvalue attains the minimum among all connected graphs of fixed order and given number of cut vertices, and then obtain a lower bound for the least eigenvalue of a connected graph in terms of the number of cut vertices. During the discussion we also get some results for the spectral radius of a connected bipartite graph and its upper bound.     

一种连续的谱聚类优化模型

聚类与图的划分问题在大数据分析中有着重要的应用.这类问题一般被描述为组合优化问题,因此较难快速求解.本文设计了一种新的连续优化模型,并提出了一种块坐标下降算法,数值实验显示我们的新方法在求解聚类与图的划分问题上很有潜力.我们还更进一步分析了我们的连续优化模型和组合优化模型的关系.     

具有割点的标号Euler图的计数

本文讲座了具有k(k≥2）个割点,并且所有割点均分布在一个2－连能Euler图的标号Euler图的计数,在这里给出了有含有n个2－连能Euler图和k(k≥2）个割点,并且所有割点均分布在其中一2－连能Euler图的标号Euler图的指数型生成函数。