Search

Highlights • we use background weight map to provide seeds for manifold ranking. • we extend the traditional manifold ranking to second-order formula. • we establish a third-order smoothness framework to optimize the saliency map. Abstract Graph-based approaches for saliency detection have attracted much attention and been exploited widely in recent years. In this paper, we present a new method to promote the performance of existing manifold ranking algorithms. Initially, we use background weight map to provide seeds for manifold ranking; Next, we extend the traditional manifold ranking to second-order formula and add a weight mask to its fitting term. Finally, for further improvement of the performance, we establish a third-order smoothness framework to optimize the saliency map. In the experiments, we compare two versions (manifold ranking with and without optimization) of our model with seven previous methods and test them on several benchmark datasets. Different kinds of strategies are also adopted for evaluation and the results demonstrate that our method achieves the state-of-the-art. [ABSTRACT FROM AUTHOR]

Abstract Containing many classic optimization problems, the family of vertex deletion problems has an important position in algorithm and complexity study. The celebrated result of Lewis and Yannakakis gives a complete dichotomy of their complexity. It however has nothing to say about the case when the input graph is also special. This paper initiates a systematic study of vertex deletion problems from one subclass of chordal graphs to another. We give polynomial-time algorithms or proofs of NP-completeness for most of the problems. In particular, we show that the vertex deletion problem from chordal graphs to interval graphs is NP-complete. [ABSTRACT FROM AUTHOR]

Given a graph G = ( V , E ) of order n and maximum degree Δ , the NP -complete S - labeling problem consists in finding a labeling of G , i.e. a bijective mapping ϕ : V → { 1 , 2 … n } , such that SL ϕ ( G ) = ∑ u v ∈ E min { ϕ ( u ) , ϕ ( v ) } is minimized. In this paper, we study the S - labeling problem, with a particular focus on algorithmic issues. We first give intrinsic properties of optimal labelings, which will prove useful for our algorithmic study. We then provide lower bounds on SL ϕ ( G ) , together with a generic greedy algorithm, which collectively allow us to approximate the problem in several classes of graphs—in particular, we obtain constant approximation ratios for regular graphs and bounded degree graphs. We also show that deciding whether there exists a labeling ϕ of G such that SL ϕ ( G ) ≤ | E | + k is solvable in O ∗ ( 2 2 k ( 2 k ) ! ) time, thus fixed-parameterized tractable in k . We finally show that the S - Labeling problem is polynomial-time solvable for two classes of graphs, namely split graphs and (sets of) caterpillars. [ABSTRACT FROM AUTHOR]

Abstract: This paper deals with problems on non-oriented edge-colored graphs. The aim is to find a route between two given vertices and . This route can be a walk, a trail or a path. Each time a vertex is crossed by a walk there is an associated non-negative reload cost , where and denote, respectively, the colors of successive edges in this walk. The goal is to find a route whose total reload cost is minimum. Polynomial algorithms and proofs of NP-hardness are given for particular cases: when the triangle inequality is satisfied or not, when reload costs are symmetric (i.e., ) or asymmetric. We also investigate bounded degree graphs and planar graphs. We conclude the paper with the traveling salesman problem with reload costs. [Copyright &y& Elsevier]

Abstract: Grid computing system is different from conventional distributed computing systems by its focus on large-scale resource sharing and open architecture for services. The global grid technologies and the Globus Toolkit in particular, are evolving toward an open grid service architecture (OGSA) with which a grid system provides an extensible infrastructure so that various organizations can offer their own services and integrate their resources. Hence, this paper aims at solving the problem of optimally allocating services on the grid to maximize the grid service reliability. Since no existing study has analyzed the grid service reliability, this paper develops initial modeling and evaluation algorithms to evaluate the grid service reliability. Based on the grid service reliability evaluation, we present an optimization model for the grid service allocation problem and develop a genetic algorithm (GA) to effectively solve it. A numerical example is given to show the modeling procedures and efficiency of the GAs. [Copyright &y& Elsevier]

This paper deals with optimization problems on rotagraphs and fasciagraphs. These graphs are repetitive structures that generalize grids and toroidal grids, respectively. We develop a theoretical framework and get linear-time and constant-time generic algorithms for wide classes of combinatorial problems which are defined in a purely combinatorial way. These classes of problems include in particular many classical optimization problems that are NP-complete in general. Our results unify in a single framework many results of the literature, in particular on the topic of domination–and its variants–in grids. [ABSTRACT FROM AUTHOR]

For two positive integers m , k and a connected graph G = ( V , E ) with a nonnegative vertex weight function w , the balanced m -connected k -partition problem, denoted as BC m P k , is to find a partition of V into k disjoint nonempty vertex subsets ( V 1 , V 2 , … , V k ) such that each G [ V i ] (the subgraph of G induced by V i ) is m -connected, and min 1 ≤ i ≤ k ⁡ { w ( V i ) } is maximized. The optimal value of BC m P k on graph G is denoted as β m ⁎ ( G , k ) , that is, β m ⁎ ( G , k ) = max ⁡ min 1 ≤ i ≤ k ⁡ { w ( V i ) } , where the maximum is taken over all m -connected k -partition of G . In this paper, we study the BC 2 P k problem on interval graphs, and obtain the following results. (1) For k = 2 , a 4/3-approximation algorithm is given for BC 2 P 2 on 4-connected interval graphs. (2) In the case that there exists a vertex v with weight at least W / k , where W is the total weight of the graph, we prove that the BC 2 P k problem on a 2 k -connected interval graph G can be reduced to the BC 2 P k − 1 problem on the ( 2 k − 1 ) -connected interval graph G − v . In the case that every vertex has weight at most W / k , we prove a lower bound β 2 ⁎ ( G , k ) ≥ W / ( 2 k − 1 ) for 2 k -connected interval graph G . (3) Assuming that weight w is integral, a pseudo-polynomial time algorithm is obtained. Combining this pseudo-polynomial time algorithm with the above lower bound, a fully polynomial time approximation scheme (FPTAS) is obtained for the BC 2 P k problem on 2 k -connected interval graphs. [ABSTRACT FROM AUTHOR]

Collective classification (CC) is a task to jointly classifying related instances of network data. Enabling CC usually improves the performance of predictive models on fully-labeled training networks with large amount of labeled data. However, acquiring such labels can be difficult and costly, and learning a CC classifier with only a few labeled data can lead to poor performance. On the other hand, there are usually large amount of unlabeled data available in practical. This naturally motivates semi-supervised collective classification (SSCC) approaches for leveraging the unlabeled data to improve CC from a sparsely-labeled network. In this paper, we propose a novel non-negative matrix factorization (NMF) based SSCC algorithm, called NMF-SSCC, to effectively learn a data representation by exploiting both labeled and unlabeled data on the network. Our idea is to use matrix factorization to obtain a compact representation of network data which uncovers the class discrimination of the data inferred from the labeled instances and simultaneously respects the intrinsic network structure. To achieve this, we design a new matrix factorization objective function and incorporate a label matrix factorization term as well as a network regularization term into it. An efficient optimization algorithm using the multiplicative updating rules is then developed to solve the new objective function. To further boost the predicting performance, we extend the proposed NMF-SSCC method into an ensemble scheme, called NMFE-SSCC, in terms of building a classification ensemble with a set of NMF-SSCC collective classifiers using different constructed latent graphs. Each NMF-SSCC classifier is learnt from one latent graph generated with various latent linkages for effectively label propagation. Experimental results on real-world data sets have demonstrated the effectiveness of the new methods. [ABSTRACT FROM AUTHOR]

Abstract: A graph is a unipolar graph if there exists a partition such that is a clique and induces the disjoint union of cliques. The complement-closed class of generalized split graphs contains those graphs such that either or the complement of is unipolar. Generalized split graphs are a large subclass of perfect graphs. In fact, it has been shown that almost all -free (and hence, almost all perfect graphs) are generalized split graphs. In this paper, we present a recognition algorithm for unipolar graphs that utilizes a minimal triangulation of the given graph, and produces a partition when one exists. Our algorithm has running time , where is the number of edges added in a minimal triangulation of the given graph. Generalized split graphs can be recognized via this algorithm in time. We give algorithms on unipolar graphs for finding a maximum independent set and a minimum clique cover in time, and for finding a maximum clique and a minimum proper coloring in time, when a unipolar partition is given. These algorithms yield algorithms for the four optimization problems on generalized split graphs that have the same worst-case time bounds. We also report that the perfect code problem is NP-complete for chordal unipolar graphs. [Copyright &y& Elsevier]

Abstract: Depth video is vital to the representation of the dynamic 3-D video, which is the fundamental for the rapidly growing 3-D video applications. The issues of accuracy and temporal consistency are the main concerns of the researches on depth videos. In previous works, the stereo matching methods with global optimization can generate accurate and dense depth videos. However, the global optimization is computationally intensive, and the temporal consistency is obtained with difficulty in the optimization procedure. In this paper, a Bayesian framework is proposed to generate accurate and temporal consistent dense depth videos in an efficient way. Firstly, the spatial and temporal correlations in 3-D videos from different viewpoints are used to generate the candidates for depth, and these correlations are further measured by extracted features. These features are adopted to estimate the risk of initial depth in our Bayesian framework. Then, a two-stage decision method is designed to select candidates of depth value in the initial depth map with the minimum risk probability. Finally, depth videos are refined by improved graph cuts algorithm with global optimization. An improved graph construction method is designed and applied on graph cuts algorithm to reduce the number of nodes in graph and thus the complexity of global optimization. The experimental results demonstrate that the proposed algorithm can achieve accurate depth videos with higher efficiency up to 68.14% than traditional methods. [Copyright &y& Elsevier]

Abstract: This paper presents new graph-cut based optimization algorithms for image processing problems. Popular graph-cut based algorithms give approximate solutions and are based on the concept of partition move. The main contribution of this work consists in proposing novel partition moves called multilabel moves to minimize Markov random field (MRF) energies with convex prior and any likelihood energy functions. These moves improve the optimum quality of the state-of-the-art approximate minimization algorithms while controlling the memory need of the algorithm at the same time. Thus, the two challenging problems, improving local optimum quality and reducing required memory for graph construction are handled with our approach. These new performances are illustrated on some image processing experiments, such as image restoration and InSAR phase unwrapping. [Copyright &y& Elsevier]

Abstract: In this paper, we consider the minimum flow problem on network flows in which the lower arc capacities vary with time. We will show that this problem for set {0,1,…, T} of time points can be solved by at most n minimum flow computations, by combining of preflow-pull algorithm and reoptimization techniques (no matter how many values of T are given). Running time of the presented algorithm is O(n 2 m). [Copyright &y& Elsevier]

Abstract: Finding shortest paths is a fundamental problem in graph theory, which has a large amount of applications in many areas like computer science, operations research, network routing and network analysis. Although many exact and approximate algorithms have been proposed, it is still a time-consuming task to calculate shortest paths for large-scale networks with tremendous volume of data available in recent years. In this paper, we find that the classic Dijkstra''s algorithm can be improved by simple modification. We propose a fast algorithm which utilize the preiously-calculated results to accelerate the latter calculation. Simple optimization strategies are also proposed with consideration of characteristics of scale-free complex networks. Our experimental results show that the average running time of our algorithm is lower than the Dijkstra''s algorithm by a factor relating to the connection probability in random networks of ER model. The performance of our algorithm is significantly better than the Dijkstra''s algorithm in scale-free networks generated by the AB model. The results show that the time complexity is reduced to about O(n2.4) in scalefree complex networks. When the optimization strategies are applied, the algorithm performance is further improved slightly in scale-free networks. [Copyright &y& Elsevier]

Abstract: Clique-width is a relatively new parameterization of graphs, philosophically similar to treewidth. Clique-width is more encompassing in the sense that a graph of bounded treewidth is also of bounded clique-width (but not the converse). For graphs of bounded clique-width, given the clique-width decomposition, every optimization, enumeration or evaluation problem that can be defined by a monadic second-order logic formula using quantifiers on vertices, but not on edges, can be solved in polynomial time. This is reminiscent of the situation for graphs of bounded treewidth, where the same statement holds even if quantifiers are also allowed on edges. Thus, graphs of bounded clique-width are a larger class than graphs of bounded treewidth, on which we can resolve fewer, but still many, optimization problems efficiently. One of the major open questions regarding clique-width is whether graphs of clique-width at most , for fixed , can be recognized in polynomial time. In this paper, we present the first polynomial-time algorithm () to recognize graphs of clique-width at most 3. [Copyright &y& Elsevier]

Abstract: In this paper we show that the problem of identifying an edge of a graph such that there exists an optimal vertex cover of containing exactly one of the vertices and is NP-hard. Such an edge is called a weak edge. We then develop a polynomial time approximation algorithm for the vertex cover problem with performance guarantee , where is an upper bound on a measure related to a weak edge of a graph. A related problem of identifying an edge such that there exists an optimal vertex cover containing both vertices and is also shown to be NP-hard. Further, we discuss a new relaxation of the vertex cover problem which is used in our approximation algorithm to obtain smaller values of . We also obtain linear programming representations of the vertex cover problem on special graphs. [Copyright &y& Elsevier]

Abstract: In this paper, we deal with several reoptimization variants of the Steiner tree problem in graphs obeying a sharpened β-triangle inequality. A reoptimization algorithm exploits the knowledge of an optimal solution to a problem instance for finding good solutions for a locally modified instance. We show that, in graphs satisfying a sharpened triangle inequality (and even in graphs where edge-costs are restricted to the values 1 and for an arbitrary small ), Steiner tree reoptimization still is NP-hard for several different types of local modifications, and even APX-hard for some of them. As for the upper bounds, for some local modifications, we design linear-time -approximation algorithms, and even polynomial-time approximation schemes, whereas for metric graphs , none of these reoptimization variants is known to permit a PTAS. As a building block for some of these algorithms, we employ a 2β-approximation algorithm for the classical Steiner tree problem on such instances, which might be of independent interest since it improves over the previously best known ratio for any . [Copyright &y& Elsevier]

Abstract: Graph drawing problems can be applied to many reality places, which also deduce to some important graph drawing problems. Such as aesthetics criteria whose optimization can lead to acceptable drawings. This paper gives an algorithm for optimizing these criteria. We propose a new force-directed model to solve the graph drawing problems in 2-D frames and modify this hybrid force model to promote to normal drawing frame shape, especially regular triangle and circle drawing frames. For the regular triangle drawing frame, it can be applied to tree drawing problems and for the circle drawing frame shape we use it to suit the normal graph drawing problems. [Copyright &y& Elsevier]

Abstract: The phase I maximum flow and most positive cut methods are used to solve the feasibility problem. Both of these methods take one maximum flow computation. Thus the feasibility problem can be solved using maximum flow algorithms. Let n and m be the number of nodes and arcs, respectively. In this paper, we present an algorithm to solve the feasibility problem with integer lower and upper bounds. The running time of our algorithm is O(mn log (nU)), where U is the value of maximum upper bound. Our algorithm improves the O(m 2 log (nU))-time algorithm in . Hence the current algorithm improves the running time in by a factor of n. Sleator and Goldberg’s algorithm is one of the well-known maximum flow algorithms, which runs in O(mn log n) time, see . Under similarity assumption , our algorithm runs in O(mn log n) time, which is the running time of Sleator and Goldberg’s algorithm. The merit of our algorithm is that, in the case of infeasibility of the given network, it not only diagnoses infeasibility but also presents some information that is useful to modeler in estimating the maximum cost of adjusting the infeasible network. [Copyright &y& Elsevier]

Abstract: This paper is devoted to the consideration of an algorithm for sequential optimization of paths in directed graphs relative to di_erent cost functions. The considered algorithm is based on an extension of dynamic programming which allows to represent the initial set of paths and the set of optimal paths after each application of optimization procedure in the form of a directed acyclic graph. [Copyright &y& Elsevier]

Abstract: We consider the problem of matching people to items, where each person ranks a subset of items in an order of preference, possibly involving ties. There are several notions of optimality about how to best match a person to an item; in particular, popularity is a natural and appealing notion of optimality. A matching is popular if there is no matching such that the number of people who prefer to exceeds the number who prefer to . However, popular matchings do not always provide an answer to the problem of determining an optimal matching since there are simple instances that do not admit popular matchings. This motivates the following extension of the popular matchings problem: [•] Given a graph where is the set of people and is the set of items, and a list denoting upper bounds on the number of copies of each item, does there exist such that for each , having copies of the -th item, where , enables the resulting graph to admit a popular matching? In this paper we show that the above problem is NP-hard. We show that the problem is NP-hard even when each is 1 or 2. We show a polynomial time algorithm for a variant of the above problem where the total increase in copies is bounded by an integer . [Copyright &y& Elsevier]

Abstract: This paper considers a new class of network flows, called dynamic generative network flows in which, the flow commodity is dynamically generated at a source node and dynamically consumed at a sink node and the arc-flow bounds are time dependent. Then the maximum dynamic flow problem in such networks for a pre-specified time horizon T is defined and mathematically formulated in both arc flow and path flow presentations. By exploiting the special structure of the problem, an efficient algorithm is developed to solve the general form of the dynamic problem as a minimum cost static flow problem. [Copyright &y& Elsevier]

Abstract: A large number of networks in the real world have a scale-free structure, and the parameters of the networks change stochastically with time. Searching for the shortest paths in a scale-free dynamic and stochastic network is not only necessary for the estimation of the statistical characteristics such as the average shortest path length of the network, but also challenges the traditional concepts related to the “shortest path” of a network and the design of path searching strategies. In this paper, the concept of shortest path is defined on the basis of a scale-free dynamic and stochastic network model, and a temporal ant colony optimization (TACO) algorithm is proposed for searching for the shortest paths in the network. The convergence and the setup for some important parameters of the TACO algorithm are discussed through theoretical analysis and computer simulations, validating the effectiveness of the proposed algorithm. [Copyright &y& Elsevier]

Abstract: Discovering a community structure is fundamental for uncovering the links between structure and function in complex networks. In this paper, we discuss an equivalence of the objective functions of the symmetric nonnegative matrix factorization (SNMF) and the maximum optimization of modularity density. Based on this equivalence, we develop a new algorithm, named the so-called SNMF-SS, by combining SNMF and a semi-supervised clustering approach. Previous NMF-based algorithms often suffer from the restriction of measuring network topology from only one perspective, but our algorithm uses a semi-supervised mechanism to get rid of the restriction. The algorithm is illustrated and compared with spectral clustering and NMF by using artificial examples and other classic real world networks. Experimental results show the significance of the proposed approach, particularly, in the cases when community structure is obscure. [Copyright &y& Elsevier]

Abstract: A spanning caterpillar in a graph is a tree composed by a path such that all vertices not in the path are leaves. In the Minimum Spanning Caterpillar Problem (MSCP) each edge has two costs: a path cost when it belongs to the path and a connection cost when it is incident to a leaf. The goal is to find a spanning caterpillar minimizing the sum of all path and connection costs. In this paper we formulate the as a minimum Steiner arborescence problem. This reduction is the basis for the development of an efficient branch-and-cut algorithm for the MSCP. We als developed a GRASP heuristic to generate primal bounds. Experiments carried out on instances adapted from TSPLIB 2.1 revealed that the exact algorithm is capable to solve to optimality instances with up to 300 vertices in reasonable time. They also showed that our heuristic yields very high quality solutions. [Copyright &y& Elsevier]

Abstract: Let G be a graph with n vertices which is embedded in Euclidean space . For any two vertices of G, their dilation is defined to be the ratio of the length of a shortest connecting path in G to the Euclidean distance between them. In this paper, we study the spectrum of the dilation, over all pairs of vertices of G. For paths, cycles, and trees in , we present -time randomized algorithms that compute, for a given value , the exact number of vertex pairs of dilation at most κ. Then we present deterministic algorithms that approximate the number of vertex pairs of dilation at most κ to within a factor of . They run in time for paths and cycles, and in time for trees, in any constant dimension d. [Copyright &y& Elsevier]

Abstract: We consider the edge-partition problem, which is a graph theoretic problem arising in the design of Synchronous Optical Networks. The deterministic edge-partition problem considers an undirected graph with weighted edges, and simultaneously assigns nodes and edges to subgraphs such that each edge appears in exactly one subgraph, and such that no edge is assigned to a subgraph unless both of its incident nodes are also assigned to that subgraph. Additionally, there are limitations on the number of nodes and on the sum of edge weights that can be assigned to each subgraph. In this paper, we consider a stochastic version of the edge-partition problem in which we assign nodes to subgraphs in a first stage, realize a set of edge weights from a finite set of alternatives, and then assign edges to subgraphs. We first prescribe a two-stage cutting plane approach with integer variables in both stages, and examine computational difficulties associated with the proposed cutting planes. As an alternative, we prescribe a hybrid integer programming/constraint programming algorithm capable of solving a suite of test instances within practical computational limits. [Copyright &y& Elsevier]

Abstract: Shortest-path problem is well-known optimization problem and has been studied by many authors in recent years. Typically it is solved by using the famous Dijkstra''s algorithm, which would quickly provide a global optimization solution in most instances. However, as the problem scale increases, this method is inefficient and may consume a considerable amount of CPU time. Neural networks, which are massively parallel models, can solve this question easily. This paper presents a novel biological neural network based algorithm for the finding of the shortest path in large scale systems. The start neuron fires first, and then the firing event spreads out through the lateral connections among the neurons, like the propagation of a wave. Then the generated spiking wave spreads at a constant speed so that the time of travel between two neurons is proportional to the path length between them. The computational complexity of the algorithm is only related to the length of the shortest path, and independent of the number of existing paths in the graph. Simulation results show that the proposed method is more efficient than Dijkstra''s in the larger scale systems. [Copyright &y& Elsevier]

Abstract: The adoption of the stress-majorization method from multi-dimensional scaling into graph layout has provided an improved mathematical basis and better convergence properties for so-called “force-directed placement” techniques. In this paper we explore algorithms for augmenting such stress-majorization techniques with simple linear constraints using gradient-projection optimization techniques. Our main focus is a particularly simple class of constraints called “orthogonal-ordering constraints” but we also discuss how gradient-projection methods may be extended to solve more general linear “separation constraints”. In addition, we demonstrate several graph-drawing applications where these types of constraints can be very useful. [Copyright &y& Elsevier]

Abstract: We study 0–1 reformulations of the multicommodity capacitated network design problem, which is usually modeled with general integer variables to represent design decisions on the number of facilities to install on each arc of the network. The reformulations are based on the multiple choice model, a generic approach to represent piecewise linear costs using 0–1 variables. This model is improved by the addition of extended linking inequalities, derived from variable disaggregation techniques. We show that these extended linking inequalities for the 0–1 model are equivalent to the residual capacity inequalities, a class of valid inequalities derived for the model with general integer variables. In this paper, we compare two cutting-plane algorithms to compute the same lower bound on the optimal value of the problem: one based on the generation of residual capacity inequalities within the model with general integer variables, and the other based on the addition of extended linking inequalities to the 0–1 reformulation. To further improve the computational results of the latter approach, we develop a column-and-row generation approach; the resulting algorithm is shown to be competitive with the approach relying on residual capacity inequalities. [Copyright &y& Elsevier]

Abstract: This paper concerns the reverse 2-median problem on trees and the reverse 1-median problem on graphs that contain exactly one cycle. It is shown that both models under investigation can be transformed to an equivalent reverse 2-median problem on a path. For this new problem an algorithm is proposed, where n is the number of vertices of the path. It is also shown that there exists an integral solution if the input data are integral. [Copyright &y& Elsevier]

Abstract: The degree-constrained minimum spanning tree (DCMST) is an NP-hard problem in graph theory. It consists of finding a spanning tree whose vertices should not exceed some given maximum degrees and whose total edge length is minimal. In this paper, novel mathematical properties for DCMST are indicated which lead to a new reduction algorithm that can significantly reduce the size of the problem. Also an algorithm for DCMST to solve the smaller problem is presented which has been preprocessed by reduction algorithm. [Copyright &y& Elsevier]

Abstract: Different algorithms, which take both links and link weights into account for the community structure of weighted networks, have been reported recently. Based on the measure of similarity among community structures introduced in our previous work, in this paper, accuracy and precision of three algorithms are investigated. Results show that Potts model based algorithm and weighted extremal optimization (WEO) algorithm work well on both dense or sparse weighted networks, while weighted Girvan–Newman (WGN) algorithm works well only for relatively sparse networks. [Copyright &y& Elsevier]

Graph orientation is a well-studied area of combinatorial optimization, one that provides a link between directed and undirected graphs. An important class of questions that arise in this area concerns orientations with connectivity requirements. In this paper we focus on how similar questions can be asked about hypergraphs, and we show that often the answers are also similar: many known graph orientation theorems can be extended to hypergraphs, using the familiar uncrossing techniques. Our results also include a short proof and an extension of a theorem of Khanna et al. (Proceedings of the Eleventh Annual ACM–SIAM Symposium on Discrete Alogrithm, 2001, pp. 663–671), and a new orientation theorem that provides a characterization for (2k+1)-edge-connected graphs. [Copyright &y& Elsevier]