We prove that claw-free graphs, containing an induced dominating path, have a Hamiltonian path, and that 2-connected claw-free graphs, containing an induced doubly dominating cycle or a pair of vertices such that ther...
详细信息
We prove that claw-free graphs, containing an induced dominating path, have a Hamiltonian path, and that 2-connected claw-free graphs, containing an induced doubly dominating cycle or a pair of vertices such that there exist two internally disjoint induced dominating paths connecting them, have a Hamiltonian cycle. As a consequence, we obtain linear time algorithms for both problems if the input is restricted to (claw, net)-free graphs. These graphs enjoy those interesting structural properties.
We present in this paper two simple linearalgorithms that solve to optimality the linear ordering problem for unweighted tree based graphs viz. the oriented trees and the oriented divide-and-conquer graphs.
We present in this paper two simple linearalgorithms that solve to optimality the linear ordering problem for unweighted tree based graphs viz. the oriented trees and the oriented divide-and-conquer graphs.
Region labelling is one of the essential preprocessing operations in an image understanding system. In this paper we present two region labelling algorithms for a multiprocessor architecture with a time complexity of ...
详细信息
Region labelling is one of the essential preprocessing operations in an image understanding system. In this paper we present two region labelling algorithms for a multiprocessor architecture with a time complexity of O(n).
The problem of coding labeled trees has been widely studied in the literature and several bijective codes that realize associations between labeled trees and sequences of labels have been presented. k-trees are one of...
详细信息
The problem of coding labeled trees has been widely studied in the literature and several bijective codes that realize associations between labeled trees and sequences of labels have been presented. k-trees are one of the most natural and interesting generalizations of trees and there is considerable interest in developing efficient tools to manipulate this class of graphs, since many NP-Complete problems have been shown to be polynomially solvable on k-trees and partial k-trees. In 1970 R,nyi and R,nyi generalized the Prufer code, the first bijective code for trees, to a subset of labeled k-trees. Subsequently, non redundant codes that realize bijection between k-trees (or R,nyi k-trees) and a well defined set of strings were produced. In this paper we introduce a new bijective code for labeled k-trees which, to the best of our knowledge, produces the first coding and decoding algorithms running in lineartime with respect to the size of the k-tree.
A maximal clique is one of the most fundamental dense substructures in an undirected graph, and maximal clique enumeration (MCE) plays an essential role in densely connected subgraphs discovering. Existing algorithms ...
详细信息
A maximal clique is one of the most fundamental dense substructures in an undirected graph, and maximal clique enumeration (MCE) plays an essential role in densely connected subgraphs discovering. Existing algorithms of maximal clique enumeration employ recursive iteration of adjacent nodes as guiding thought, which incurs high time complexity. In this paper, we propose a lineartime algorithm, CM-Constructor (Candidate Map Constructor), for maximal clique enumeration in large sparse graphs which generates a novel data structure called candidate map as result. A candidate map holds not only all maximal cliques of an undirected graph but also some non-maximal cliques that can be easily discarded via an inverted clique tree. To the best of our knowledge, CM-Constructor is the first algorithm to tackle maximal clique enumeration problem utilizing linear procedure. It generates all maximal cliques without duplications for an undirected graph G = (V, E) within O (vertical bar E vertical bar) time. (C) 2017 Elsevier B.V. All rights reserved.
Recently lexicographic breadth first search (LexBFS) has been shown to be a very powerful tool for the development of lineartime, easily implementable recognition algorithms for various families of graphs. In this pa...
详细信息
Recently lexicographic breadth first search (LexBFS) has been shown to be a very powerful tool for the development of lineartime, easily implementable recognition algorithms for various families of graphs. In this paper, we add to this work by producing a simple two LexBFS sweep algorithm to recognize the family of cographs. This algorithm extends to other related graph families such as P-4-reducible, P-4-sparse, and distance hereditary. It is an open question whether our cograph recognition algorithm can be extended to a similarly easy algorithm for modular decomposition.
In this paper we are concerned with the subproblem of bin packing, where the set of possible weights of elements is finite. In [5] it was mentioned that this problem could be solved by an exhaustive search procedure i...
详细信息
In this paper we are concerned with the subproblem of bin packing, where the set of possible weights of elements is finite. In [5] it was mentioned that this problem could be solved by an exhaustive search procedure in polynomial time, but the degree of the polynomial is high and increases as the cardinality of the set of weights increases. However, we will show that a more careful analysis of the problem leads to a lineartime algorithm. The impact of this result on task scheduling is discussed.
The 2-vertex-connectivity augmentation problem of a graph with degree constraints, 2VCA-DC, is defined as follows: "Given an undirected graph G = (V, E) and an upper bound a(v;G) is an element of Z(+) boolean OR ...
详细信息
The 2-vertex-connectivity augmentation problem of a graph with degree constraints, 2VCA-DC, is defined as follows: "Given an undirected graph G = (V, E) and an upper bound a(v;G) is an element of Z(+) boolean OR {infinity} on vertex-degree increase for each v is an element of V, find a smallest set E' of edges such that (V, E boolean OR E') has at least two internally-disjoint paths between any pair of vertices in V and such that vertex-degree increase of each v is an element of V by the addition of E' to G is at most a(v;G), where Z(+) is the set of nonnegative integers." In this paper we show that checking the existence of a feasible solution and finding an optimum solution to 2VCA-DC can be done in O(vertical bar V vertical bar + vertical bar E vertical bar) time.
Medard, Finn, Barry and Gallager proposed an elegant recovery scheme (known as the MFBG scheme) using redundant trees. Xue, Chen and Thulasiraman extended the MFBG scheme and introduced the concept of quality of prote...
详细信息
ISBN:
(纸本)0780389689
Medard, Finn, Barry and Gallager proposed an elegant recovery scheme (known as the MFBG scheme) using redundant trees. Xue, Chen and Thulasiraman extended the MFBG scheme and introduced the concept of quality of protection (QoP) as a metric of multifailure recovery capabilities for single failure recovery schemes. In this paper, we present three linear time algorithms for constructing redundant trees for single link failure recovery in 2-edge connected graphs and for single node failure recovery in 2-connected graphs. Our first algorithm aims at high QoP for single link recovery schemes in 2-edge connected graphs. The previous best algorithm has a running time of O(n(2)(m + n)), where n and m are the number of nodes and links in the network. Our algorithm has a running time of 0(m + n), with comparable performance. Our second algorithm aims at high QoS for single link recovery schemes in 2-edge connected graphs. Our algorithm improves the previous best algorithm with 0 (n(2)(m + n)) time complexity to 0(m + n) time complexity with comparable performance. Our third algorithm aims at high QoS for single node recovery schemes in 2-connected graphs. Again, our algorithm improves the previous best algorithm with 0(n(2)(m + n)) time complexity to O(m + n) time complexity with comparable performance. Simulation results show that our new algorithms outperform previously known linear time algorithms significantly in terms of QoP or QoS, and outperform other known algorithms in terms of running time, with comparable QoP of QoS performance.
It is demonstrated that the linear programming problem in d variables and n constraints can be solved in O(n) time when d is fixed. This bound follows from a multidimensional search technique which is applicable for q...
详细信息
It is demonstrated that the linear programming problem in d variables and n constraints can be solved in O(n) time when d is fixed. This bound follows from a multidimensional search technique which is applicable for quadratic programming as well. There is also developed an algorithm that is polynomial in both n and d provided d is bounded by a certain slowly growing function of n.
暂无评论