求二部图的最大匹配图的一种算法

 一个图的最大匹配图是以这个图的最大匹配集作为顶点集,两个顶点相邻当且仅当这两个最大匹配恰有一条边不同.本文首先对Gallai Edmonds结构定理中的三部分顶点在二部图中进行了详细刻画.然后讨论了构造最大匹配图问题的计算复杂性.最后深入研究了二部图最大匹配图的结构性质并给出了构造二部图的最大匹配图的一种算法.     

On the reliability of a number of s-p reducible graphs

Let G=(V,E) be a graph whose edges may fail with known probabilities and let K a subset of V be specified. The overall reliability of G, denoted by R(G), is the probability that all vertices in K=V communicate with each other. We have two types of graphs, s-p reducible and s-p complex, depending on whether after series-arallel reductions the result is a single edge or not. A number of s-p reducible graphs are presented and expressions that evaluate their overall reliability are introduced.     

Vertex splitting in resistor-network analysis

By splitting selected vertices of its graph or of related graphs, the tree-enumeration problem involved in finding the equivalent resistance between two vertices of a network of resistors can often be reduced to a series of smaller and more manageable steps.     

A linear-time algorithm for computing K-terminal reliability onproper interval graphs

Consider a probabilistic graph in which the edges are perfectly reliable, but vertices can fail with some known probabilities. The K-terminal reliability of this graph is the probability that a given set of vertices K is connected. This reliability problem is #P-complete for general graphs, and remains #P-complete for chordal graphs and comparability graphs. This paper presents a linear-time algorithm for computing K-terminal reliability on proper interval graphs. A graph G = (V, E) is a proper interval graph if there exists a mapping from V to a class of intervals I of the real line with the properties that two vertices in G are adjacent if their corresponding intervals overlap and no interval in I properly contains another. This algorithm can be implemented in O(|V| + |E|) time     

图的最大权团的DNA计算

给定顶点赋权的无向图,图的最大权团问题是寻找每个顶点都相邻的顶点子集(团)具有最大权.这个问题是寻找无权图的最大团问题的推广.图的最大团和最大权团都是著名的NP-完全问题,没有非常有效的算法.1994年Adleman博士首先提出用DNA计算解决NP-完全问题,使得NP-完全问题的求解可能得到解决.本文给出了基于质粒技术的无向图的最大权团问题的DNA算法,依据Head T等的实验手段,本文提出的算法是有效并且可行的.     

The /spl Delta//sup 2/-conjecture for L(2,1)-labelings is true for direct and strong products of graphs

A variation of the channel-assignment problem is naturally modeled by L(2,1)-labelings of graphs. An L(2,1)-labeling of a graph G is an assignment of labels from {0,1,...,/spl lambda/} to the vertices of G such that vertices at distance two get different labels and adjacent vertices get labels that are at least two apart and the /spl lambda/-number /spl lambda/(G) of G is the minimum value /spl lambda/ such that G admits an L(2,1)-labeling. The /spl Delta//sup 2/-conjecture asserts that for any graph G its /spl lambda/-number is at most the square of its largest degree. In this paper it is shown that the conjecture holds for graphs that are direct or strong products of nontrivial graphs. Explicit labelings of such graphs are also constructed.     

(k,l)-递归极大平面图的结构

对于一个平面图G实施扩3-轮运算是指在G的某个三角形面xyz内添加一个新顶点v,使v与x, y, z均相邻,最后得到一个阶为|V(G)|+1的平面图的过程。一个递归极大平面图是指从平面图K₄出发,逐次实施扩3-轮运算而得到的极大平面图。 所谓一个(k,l)-递归极大平面图是指一个递归极大平面图,它恰好有k个度为3的顶点,并且任意两个3度顶点之间的距离均为l。该文对(k,l)-递归极大平面图的存在性问题做了探讨,刻画了(3,2)-及(2,3)-递归极大平面图的结构。     

Digit-pipelined on-chip clique-finding VLSI processor for real-time 3-D object recognition

A new on-chip clique-finding VLSI processor is proposed for high-speed graph matching. Using VLSI arrays with the encoded information of all the vertices, the breadth-first search algorithm that finds corresponding vertices between two graphs can be performed in a digital-level pipelining manner. The effect of the digit-pipelined architecture is evaluated.<>     

k-Diameter of Circulant Graph with Degree 3

Parameters k-distance and k-diameter are extension of the distance and the diameter in graph theory. In this paper, the k-distance dk(x,y) between the any vertices x and y is first obtained in a connected circulant graph G with order n(n is even) and degree 3 by removing some vertices from the neighbour set of the x. Then, the k-diameters of the connected circulant graphs with order n and degree 3 are given by using the k-diameter dk(x,y).     

k-Diameter of Circulant Graph with Degree 3

Parameters k-distance and k-diameter are extension of the distance and the diameter in graph theory. In this paper, the k-distance dk （x,y） between the any vertices x and y is first obtained in a connected circulant graph G with order n （n is even） and degree 3 by removing some vertices from the neighbour set of the x. Then, the k-diameters of the connected circulant graphs with order n and degree 3 are given by using the k-diameter dk （x,y）.     

L(j, k)-Labelings of Kronecker Products of Complete Graphs

For positive integers j ges k, an L(j, k)-labeling of a graph G is an integer labeling of its vertices such that adjacent vertices receive labels that differ by at least j and vertices that are distance two apart receive labels that differ by at least k. We determine lambda^j _k(G) for the case when G is a Kronecker product of finitely many complete graphs, where there are certain conditions on j and k. Areas of application include frequency allocation to radio transmitters.     

Identifying and locating-dominating codes: NP-completeness results for directed graphs

Let G=(V, A) be a directed, asymmetric graph and C a subset of vertices, and let B/sub r//sup -/(v) denote the set of all vertices x such that there exists a directed path from x to v with at most r arcs. If the sets B/sub r//sup -/(v) /spl cap/ C, v /spl isin/ V (respectively, v /spl isin/ V/spl bsol/C), are all nonempty and different, we call C an r-identifying code (respectively, an r-locating-dominating code) of G. In other words, if C is an r-identifying code, then one can uniquely identify a vertex v /spl isin/ V only by knowing which codewords belong to B/sub r//sup -/(v), and if C is r-locating-dominating, the same is true for the vertices v in V/spl bsol/C. We prove that, given a directed, asymmetric graph G and an integer k, the decision problem of the existence of an r-identifying code, or of an r-locating-dominating code, of size at most k in G, is NP-complete for any r/spl ges/1 and remains so even when restricted to strongly connected, directed, asymmetric, bipartite graphs or to directed, asymmetric, bipartite graphs without directed cycles.     

An Optimized Circuit Simulation Method for the Identification of Isomorphic Disconnected Graphs

Many algorithms exist to deal with the problem of graph isomorphism, but most of the contemporary algorithms like VF2 have a bad performance for identifying isomorphism of disconnected graphs. In this paper, we propose a method that can filter and remove single vertices so as to eliminate the dependence of the relationship between all vertices which causes the loss of effectiveness. Tests on disconnected graphs demonstrate that this method can solve the problem of identifying isomorphic disconnected graphs in polynomial time.     

Reconstructing Extended Perfect Binary One-Error-Correcting Codes From Their Minimum Distance Graphs

The minimum distance graph of a code has the codewords as vertices and edges exactly when the Hamming distance between two codewords equals the minimum distance of the code. A constructive proof for reconstructibility of an extended perfect binary one-error-correcting code from its minimum distance graph is presented. Consequently, inequivalent such codes have nonisomorphic minimum distance graphs. Moreover, it is shown that the automorphism group of a minimum distance graph is isomorphic to that of the corresponding code.      

一种计算Ad hoc网络K-终端可靠性的线性时间算法

研究计算Ad hoe网络K-终端可靠性的线性时间算法,可以快速计算Ad hoe网络K-终端可靠性。为了计算Ad hoe网络分级结构尽终端可靠性,可以采用无向概率图表示Ad hoe网络的分级结构。每个簇头由已知失效率的结点表示,并且当且仅当两个簇相邻时,两个结点间的互连由边表示。这个概率图的链路完全可靠,并且已知结点的失效率。此图的K-终端可靠性为给定K-结点集是互连的概率。文中提出了基于合适区间图计算尽终端可靠性的一种线性时间算法。本算法可用来计算Ad hoe网络的K-终端可靠性。其时间复杂度为O（｜V｜＋｜E｜）。     

Efficient VLSI architectures for a high-performance digital imagecommunication system

A typical digital image communication system based on a number of ASIC architectural designs is currently under development. After partitioning the complete system into several stages, each selected algorithm can be implemented on a single ASIC based on an efficient architectural style. The required throughput for high-performance data compression and channel coding has been obtained due to the optimization of the critical path in the architectural design. Input/output (I/O) operations, which create the bottleneck for many image-processing algorithms, are handled by a dedicated I/O interface unit. Construction of each dedicated data path in the architecture is based on a limited parameterizable functional building block (FBB) library. The dedicated data paths have been constructed by partitioning the initial signal flow graph (SFG) into compatible graphs and by matching the graphs in each partition onto a collection of time-multiplexed FBBs. Hierarchically partitioned controllers were used to meet the high-throughput requirements. The ASIC architectures proposed are oriented to broadband integrated services digital networks (B-ISDN) as well as high-performance digital image compression systems     

Total Coloring of G×Pn and G×Cn

It is proved that if G is a (△+1)-colorable graph, so are the graphs G×Pn and C×Cn, where Pn and Cn are respectively the path and cycle with n vertices, and △ the maximum edge degree of the graph. The exact chromatic numbers of the product graphs Pr1×Pr1×...×Prn× and C3k×C2m1×C2m2×...×C2mn are also presented. Thus the total coloring conjecture is proved to be true for many other graphs.     

On the optimality of solutions of the max-productbelief-propagation algorithm in arbitrary graphs

Graphical models, such as Bayesian networks and Markov random fields (MRFs), represent statistical dependencies of variables by a graph. The max-product “belief propagation” algorithm is a local-message-passing algorithm on this graph that is known to converge to a unique fixed point when the graph is a tree. Furthermore, when the graph is a tree, the assignment based on the fixed point yields the most probable values of the unobserved variables given the observed ones. Good empirical performance has been obtained by running the max-product algorithm (or the equivalent min-sum algorithm) on graphs with loops, for applications including the decoding of “turbo” codes. Except for two simple graphs (cycle codes and single-loop graphs) there has been little theoretical understanding of the max-product algorithm on graphs with loops. Here we prove a result on the fixed points of max-product on a graph with arbitrary topology and with arbitrary probability distributions (discrete- or continuous-valued nodes). We show that the assignment based on a fixed point is a “neighborhood maximum” of the posterior probability: the posterior probability of the max-product assignment is guaranteed to be greater than all other assignments in a particular large region around that assignment. The region includes all assignments that differ from the max-product assignment in any subset of nodes that form no more than a single loop in the graph. In some graphs, this neighborhood is exponentially large. We illustrate the analysis with examples     

基于跨模态对比的场景图图像生成

条件图像生成根据不同形式的输入生成符合条件的图像,其中场景图是一类具有代表性的条件输入形式。场景图将图像中的物体抽象为节点,将物体之间的关系抽象为边,是一种广泛应用在计算机视觉和跨模态领域的结构化图表示。由于场景图中包含多个物体和物体之间的关系,现有的场景图图像生成方法容易导致生成结果和条件语义不一致,例如物体缺失和关系错误等。本文提出基于跨模态对比的生成方法解决上述问题。首先,本文提出关系一致性对比使生成的物体关系和输入的边保持一致。我们设计了联合特征代表图像中的物体的关系,并拉近联合特征和与其相关的边特征的距离,使其相比于不相关的边特征距离更接近。本文引入物体一致性对比使的生成的物体区域和输入的节点保持对应。在这个部分我们使用注意力机制获得节点对应的物体特征,然后拉近相关的节点特征于物体特征的距离。最后,本文提出全局一致性对比使的生成的图像整体和输入的场景图保持一致, 该对比损失将相关联的图像和场景图特征拉近,同时将不相关的样本特征相互远离。我们COCO-stuff和VG数据集上进行了详细的实验,实验结果表明我们的方法相比当前最佳性能分别在两个数据集上提升8.33%和8.87%的FID。消融实验表明每个对比损失模块都能够提升图像的生成质量,可视化结果展示了方法对于解决上述问题的有效性。从实验结果可知,我们的方法不仅能够提升图像的生成质量,并能够有效缓解物体缺失和关系错误等语义不一致问题。      

A linear-time algorithm to compute the reliability of planarcube-free networks

A planar graph G=(V,E) is a cube-free graph (CF graph) if it has no subgraph homomorphic to the cube. The cube is the graph whose vertices and edges are the vertices and edges of the three dimensional geometric cube. The all-terminal reliability of a graph G whose edges can fail (with known probabilities) is the probability that G is connected. The problem of computing the all-terminal reliability of a general graph is NP-hard. An O(| V|) time algorithm for computing the all-terminal reliability of CF graphs is presented