Types of arcs in a fuzzy graph

The concept of connectivity plays an important role in both theory and applications of fuzzy graphs. Depending on the strength of an arc, this paper classifies arcs of a fuzzy graph into three types namely α-strong, β-strong and δ-arcs. The advantage of this type of classification is that it helps in understanding the basic structure of a fuzzy graph completely. We analyze the relation between strong paths and strongest paths in a fuzzy graph and obtain characterizations for fuzzy bridges, fuzzy trees and fuzzy cycles using the concept of α-strong, β-strong and δ-arcs. An arc of a fuzzy tree is α-strong if and only if it is an arc of its unique maximum spanning tree. Also we identify different types of arcs in complete fuzzy graphs.     

Super connectivity of line graphs

The super connectivity κ^′ and the super edge-connectivity λ^′ are more refined network reliability indices than connectivity κ and edge-connectivity λ. This paper shows that for a connected graph G with order at least four rather than a star and its line graph L(G), κ^′(L(G))=λ^′(G) if and only if G is not super-λ^′. As a consequence, we obtain the result of Hellwig et al. [Note on the connectivity of line graphs, Inform. Process. Lett. 91 (2004) 7] that κ(L(G))=λ^′(G). Furthermore, the authors show that the line graph of a super-λ^′ graph is super-λ if the minimum degree is at least three.     

Component connectivity of generalized Petersen graphs

Let G be a simple non-complete graph of order n. The r-component edge connectivity of G denoted as λ_r (G) is the minimum number of edges that must be removed from G in order to obtain a graph with (at least) r connected components. The concept of r-component edge connectivity generalizes that of edge connectivity by taking into account the number of components of the resulting graph. In this paper we establish bounds of the r component edge connectivity of an important family of interconnection network models, the generalized Petersen graphs GP(n, k) in which n and k are relatively prime integers.     

On the connectivity preserving minimum cut problem

In this paper, we study a generalization of the classical minimum cut problem, called Connectivity Preserving Minimum Cut (CPMC) problem, which seeks a minimum cut to separate a pair (or pairs) of source and destination nodes and meanwhile ensure the connectivity between the source and its partner node(s). For this problem, we consider two variants, connectivity preserving minimum node cut (CPMNC) and connectivity preserving minimum edge cut (CPMEC). For CPMNC, we show that it cannot be approximated within α logn for some constant α   unless P=NP$P=\mathit{NP}$, and cannot be approximated within any poly(logn)$\mathit{poly}(\mathit{logn})$ unless NP has quasi-polynomial time algorithms. The hardness results hold even for graphs with unit weight and bipartite graphs. For CPMEC, we show that it is in P for planar graphs.     

On m-restricted edge connectivity of undirected generalized De Bruijn graphs

An m-restricted edge cut is an edge cut of a connected graph whose removal results in components of order at least m, the minimum cardinality over all m-restricted edge cuts of a graph is its m-restricted edge connectivity. It is known that telecommunication networks with topology having larger m-restricted edge connectivity are locally more reliable for all m≤3. This work shows that if n≥7, then undirected generalized binary De Bruijn graph UB_G(2, n) is maximally m-restricted edge connected for all m≤3, where a graph G is maximally m-restricted edge connected if its m-restricted edge connectivity is equal to the minimum number of edges from any connected subgraphs S to G?S.     

A kind of conditional vertex connectivity of Cayley graphs generated by 2-trees

Let G be a graph. Then T ⊆ V(G) is called an R^k-vertex-cut if G − T is disconnected and each vertex in V(G) − T has at least k neighbors in G − T. The size of a smallest R^k-vertex-cut is the R^k-vertex-connectivity of G and is denoted by κ^k(G). In this paper, we determine the numbers κ¹ and κ² for Cayley graphs generated by 2-trees, including the popular alternating group graphs.     

Arc-based evaluation and detection of ellipses

We propose the use of elliptic arcs as a reliable criterion for ellipse evaluation and reconstruction. A technique based on pixel connectivity is developed for detecting the endpoints and subtended angles of elliptic arcs. Model-based distance and angular connectivity are introduced for quick and meaningful estimation of elliptic arcs. An iterative algorithm for multiple-ellipse fitting based on arc detection is presented. Experimental results confirm the robustness and accuracy of the algorithm for the fitting of multiple overlapping ellipses.     

Investigations on adaptive connectivity and shape prior based fuzzy graph-cut colour image segmentation

Image segmentation is a challenging problem in computer vision with wide application. It is a process which considers the similarity criterion required to separate an image into different homogenous connected regions. First, an Optimized Adaptive Connectivity and Shape Prior in Modified Graph Cut Segmentation method has been applied to handle the structural irregularities in images. Second, an Optimized Adaptive Connectivity and Shape Prior in Modified Fuzzy Graph Cut Segmentation (Opac-MFGseg) is proposed to partition the images based on feature values. In this method, a fuzzy rule based system is used with optimization algorithm to provide the information on how much a specific feature is involved in image boundaries. The graph obtained from this fuzzy approach is further used in adaptive shape prior in modified graph cuts framework. Moreover, this method supports moving images (videos). In such a situation, a fully dynamic method called Optimized Adaptive Connectivity and Shape Prior in Dynamic Fuzzy Graph Cut Segmentation (Opac-DFGseg) method is proposed for the image segmentation. The effectiveness of the Opac-MFGseg and Opac-DFGseg methods is tested in terms of average sensitivity, precision, area overlap measure, relative error, and accuracy and computation time.     

Dynamic bottleneck optimization for k-edge and 2-vertex connectivity

We consider the problem of updating efficiently the minimum value b over a weighted graph, so that edges with a cost less than b induce a spanning subgraph satisfying a k-edge or 2-vertex connectivity constraint, when the cost of an edge of the graph is updated. Our results include update algorithms of almost linear time (up to poly-logarithmic factors) in the number of vertices for all considered connectivity constraints (for fixed k), and a worst case construction showing that these algorithms are almost optimal in their class.     

A kind of conditional fault tolerance of alternating group graphs

A vertex subset F is a k-restricted vertex-cut of a connected graph G if G−F is disconnected and every vertex in G−F has at least k good neighbors in G−F. The cardinality of the minimum k-restricted vertex-cut of G is the k-restricted connectivity of G, denoted by κk(G). This parameter measures a kind of conditional fault tolerance of networks. In this paper, we show that for the n-dimensional alternating group graph AGn, κ²(AG₄)=4 and κ²(AGn)=6n−18 for n?5.     

A topological approach to dynamic graph connectivity

A dynamic connectivity problem consists of an initial graph, and a sequence of operations consisting of graph modifications and graph connectivity tests. The size n of the problem is the sum of the maximum number of vertices and edges of the derived graph, plus the number of operations to be executed. Each graph modification is a deletion of either an edge or an isolated vertex. Each graph connectivity test is to determine if there exists a path in the current graph between two given vertices (the vertices can vary for distinct tests). The best previously known time for this dynamic connectivity problem was Ω(n²).Our main result is an O(ng+n log n) time algorithm for the dynamic connectivity problem in the case of the maximum genus of the derived graph being g.     

Super p-restricted edge connectivity of line graphs

Super restricted connectivity and super restricted edge connectivity are more refined network reliability indices than connectivity and edge connectivity. In this paper, we first introduce the concepts of super restricted connectivity and super restricted edge connectivity and then give a property of graphs with equal p-restricted edge connectivity and 1-p-restricted connectivity. Applying this property, we show a sufficient condition for a line graph to be super p-restricted edge-connected and a relationship between super 1-p-restricted connected graphs and super p-restricted edge-connected graphs.     

Component connectivity of the hypercubes

The r-component connectivity κ _r (G) of the non-complete graph G is the minimum number of vertices whose deletion results in a graph with at least r components. So, κ₂ is the usual connectivity. In this paper, we determine the r-component connectivity of the hypercube Q _n for r=2, 3, …, n+1, and we classify all the corresponding optimal solutions.     

Combinatorial algorithms for feedback problems in directed graphs

Given a weighted directed graph G=(V,A), the minimum feedback arc set problem consists of finding a minimum weight set of arcs A′⊆A such that the directed graph (V,A?A′) is acyclic. Similarly, the minimum feedback vertex set problem consists of finding a minimum weight set of vertices containing at least one vertex for each directed cycle. Both problems are NP-complete. We present simple combinatorial algorithms for these problems that achieve an approximation ratio bounded by the length, in terms of number of arcs, of a longest simple cycle of the digraph.     

基于分层递阶商空间链的图连通性研究

图连通性的判定对于路径规划中任意两点间路径相通性判断以及连通块的划分都具有重要意义。从节点的边连通关系着手分析图的结构层次,通过构建图的分层递阶商空间链,分析不同层次商空间链中各节点分布情况,得出新的图连通性判定方法。与以往各判定方法相比,该方法具有易实现、效率高的优点,不仅能有效地判定图是否连通,还能确定图的连通分支数以及哪些节点位于同一连通分支中。     

An efficient network flow code for finding all minimum cost s–t cutsets

Cutset algorithms have been well documented in the operations research literature. A directed graph is used to model the network, where each node and arc has an associated cost to cut or remove it from the graph. The problem considered in this paper is to determine all minimum cost sets of nodes and/or arcs to cut so that no directed paths exist from a specified source node s to a specified sink node t. By solving the dual maximum flow problem, it is possible to construct a binary relation associated with an optimal maximum flow such that all minimum cost s–t cutsets are identified through the set of closures for this relation. The key to our implementation is the use of graph theoretic techniques to rapidly enumerate this set of closures. Computational results are presented to suggest the efficiency of our approach.Scope and purposeThis paper describes the technical details of a network flow algorithm used to find all minimum cost s–t cutsets in any network topology. The motivation for this work was to provide additional automated analysis capability to a military network targeting system. Specifically, the problem is to identify a minimum cost set of nodes and/or arcs that when removed from the network, will disconnect a selected pair of origin–destination nodes. Algorithms for solving this problem are well understood, with an active research thrust in both the operations research and computer science academic communities in developing more efficient algorithms for larger networks. The main contribution of this paper is in extending these algorithms to quickly find all minimum cost cutset solutions. The implementation described in this paper outperformed conventional methods by several orders of magnitude on networks having thousands of nodes and arcs, with empirical solution times that grew linearly with the network size. The results translate to a real-time cutset analysis capability to support military targeting applications.     

Conditional connectivity of Cayley graphs generated by transposition trees

Given a graph G and a non-negative integer h, the Rh-(edge)connectivity of G is the minimum cardinality of a set of (edges)vertices of G, if any, whose deletion disconnects G, and every remaining component has minimum degree at least h. Similarly, given a non-negative integer g, the g-(edge)extraconnectivity of G is the minimum cardinality of a set of (edges)vertices of G, if any, whose deletion disconnects G, and every remaining component has more than g vertices. In this paper, we determine R₂-(edge)connectivity and 2-extra(edge)connectivity of Cayley graphs generated by transposition trees.     

A probabilistic algorithm for vertex connectivity of graphs

A probabilistic algorithm is presented which computes the vertex connectivity of an undirected graph G = (V,E) in expected time $\text{O((-log ε|V|}{}^{\mathrm{<mtext>3</mtext><mtext>2</mtext>}}\text{|E|)}$ with error probability at most e provided that |E|<frcase|1/2d|V|² for some universal constant d<1.     

Parameterized algorithms for feedback set problems and their duals in tournaments

The parameterized feedback vertex (arc) set problem is to find whether there are k vertices (arcs) in a given graph whose removal makes the graph acyclic. The parameterized complexity of this problem in general directed graphs is a long standing open problem. We investigate the problems on tournaments, a well studied class of directed graphs. We consider both weighted and unweighted versions.     

Super connectivity of Kronecker products of graphs

Let G₁ and G₂ be two connected graphs. The Kronecker product G₁×G₂ has vertex set V(G₁×G₂)=V(G₁)×V(G₂) and the edge set . In this paper, we show that if G is a bipartite graph with κ(G)=δ(G), then G×Kn(n?3) is super-κ.