๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

An Efficient NC Algorithm for a Sparse k-Edge-Connectivity Certificate

โœ Scribed by Hiroshi Nagamochi; Toru Hasunuma

Publisher
Elsevier Science
Year
2001
Tongue
English
Weight
166 KB
Volume
38
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

โœฆ Synopsis

We present an efficient algorithm for finding a sparse k-edge-connectivity certificate of a multigraph G. Our algorithm runs in O log kn log k 2 log n 2 time using O k n + m processors on an ARBITRARY CRCW PRAM, where n and m stand for the numbers of vertices in G and edges in the simplified graph of G, respectively.

๐Ÿ“œ SIMILAR VOLUMES

An algorithm for construction of a k-con
An algorithm for construction of a k-connected graph with minimum number of edges and quasiminimal diameter
โœ Ulrich Schumacher ๐Ÿ“‚ Article ๐Ÿ“… 1984 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 470 KB

Two fundamental considerations in the design of a communication network are reliability and maximum transmission delay. In this paper we give an algorithm for construction of an undirected graph with n vertices in which there are k node-disjoint paths between any two nodes. The generated graphs will

An efficient adaptive algorithm for edge
An efficient adaptive algorithm for edge detection based on the likelihood ratio test
โœ A. De Santis; D. Iacoviello ๐Ÿ“‚ Article ๐Ÿ“… 2002 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 653 KB

## Abstract The edge detection problem in blurred and noisy 2โ€D signals is dealt with. An adaptive signal processing algorithm is proposed which marks edge points according to an hypothesis test which compares the likelihoods of two models describing the local signal behaviour in the two cases of a

An Inexact Newton Algorithm for Solving
An Inexact Newton Algorithm for Solving the Tokamak Edge Plasma Fluid Equations on a Multiply-Connected Domain
โœ D.A. Knoll; P.R. McHugh ๐Ÿ“‚ Article ๐Ÿ“… 1995 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 554 KB

Newton's method is combined with a preconditioned conjugate gradient-like algorithm and finite volume discretization to solve the steady-state two-dimensional tokamak edge plasma fluid equations. A numerical evaluation of the Jacobian is employed. Mesh sequencing, pseudo-transient continuation, and