A Faster Deterministic Maximum Flow Algorithm

Cheriyan and Hagerup developed a randomized algorithm to compute the maximum flow in a graph with n nodes and m edges in O(mn + n² log²n) expected time. The randomization is used to efficiently play a certain combinatorial game that arises during the computation. We give a version of their algorithm where a general version of their game arises. Then we give a strategy for the game that yields a deterministic algorithm for computing the maximum flow in a directed graph with n nodes and m edges that runs in time O(mn(log_{m/n log n}n)). Our algorithm gives an O(mn) deterministic algorithm for all m/n = Ω(n^ε) for any positive constant ε, and is currently the fastest deterministic algorithm for computing maximum flow as long as m/n = ω(log n).     

Use of dynamic trees in a network simplex algorithm for the maximum flow problem

Goldfarb and Hao (1990) have proposed a pivot rule for the primal network simplex algorithm that will solve a maximum flow problem on ann-vertex,m-arc network in at mostnm pivots and O(n ² m) time. In this paper we describe how to extend the dynamic tree data structure of Sleator and Tarjan (1983, 1985) to reduce the running time of this algorithm to O(nm logn). This bound is less than a logarithmic factor larger than those of the fastest known algorithms for the problem. Our extension of dynamic trees is interesting in its own right and may well have additional applications.Research partially supported by a Presidential Young Investigator Award from the National Science Foundation, Grant No. CCR-8858097, an IBM Faculty Development Award, and AT&T Bell Laboratories.Research partially supported by the Office of Naval Research, Contract No. N00014-87-K-0467.Research partially supported by the National Science Foundation, Grant No. DCR-8605961, and the Office of Naval Research, Contract No. N00014-87-K-0467.     

Need and use of reference materials in a comprehensive countrywide monitoring of radionuclides

The reliability of measurement results is essential for forming a common database of a laboratory network, because a well-maintained and consistent database is the crucial point of countrywide monitoring. Reference materials are important tools in realizing some aspects of quality assurance; they are especially useful in harmonizing work within the network. Among usual types of reference materials in radio analytics solutions, matrix reference materials and some special reference objects are used. All classes of reference materials should be used depending on the purpose of the demonstration of quality, even in-house reference materials. Interlaboratory measurement comparison and performance evaluation programs play important quality assurance role in radio analytical laboratories. Fortunately, nowadays, the main task is to determine a very low radioactivity concentration in the environment; therefore, pre-concentration is necessary. Generally, the radionuclide bearing natural materials collected from sites where there had been sufficient time for natural processes to redistribute various chemically different species of radionuclides are more reliable reference materials than spiked materials—the main difference is the chemical bounding which is crucial from the point of view of the bioavailability. The need of reference material is summarized according to the intended use, like quality control, measurement validation, and instrument calibration.     

A simple version of Karzanov's blocking flow algorithm

Dinic has shown that the classic maximum flow problem on a graph of n vertices and m edges can be reduced to a sequence of at most n ? 1 so-called ‘blocking flow’ problems on acyclic graphs. For dense graphs, the best time bound known for the blocking flow problems is O(n²). Karzanov devised the first O(n²)-time blocking flow algorithm, which unfortunately is rather complicated. Later Malhotra, Kumar and Maheshwari devise another O(n²)-time algorithm, which is conceptually very simple but has some other drawbacks. In this paper we propose a simplification of Karzanov's algorithm that is easier to implement than Malhotra, Kumar and Maheshwari's method.     

Efficient algorithms for a family of matroid intersection problems

Consider a matroid where each element has a real-valued cost and a color, red or green; a base is sought that contains q red elements and has smallest possible cost. An algorithm for the problem on general matroids is presented, along with a number of variations. Its efficiency is demonstrated by implementations on specific matroids. In all cases but one, the running time matches the best-known algorithm for the problem without the red element constraint: On graphic matroids, a smallest spanning tree with q red edges can be found in time O(n log n) more than what is needed to find a minimum spanning tree. A special case is finding a smallest spanning tree with a degree constraint; here the time is only O(m + n) more than that needed to find one minimum spanning tree. On transversal and matching matroids, the time is the same as the best-known algorithms for a minimum cost base. This also holds for transversal matroids for convex graphs, which model a scheduling problem on unit-length jobs with release times and deadlines. On partition matroids, a linear-time algorithm is presented. Finally an algorithm related to our general approach finds a smallest spanning tree on a directed graph, where the given root has a degree constraint. Again the time matches the best-known algorithm for the problem without the red element (i.e., degree) constraint.     

Finding a feasible flow in a strongly connected network

We give a linear-time algorithm to find a feasible flow in a strongly connected network with fixed supplies and demands, each summing to a common value that is at most the minimum arc capacity. This algorithm speeds up the Goldberg-Rao maximum flow method by a constant factor.     

Efficient algorithms for finding minimum spanning trees in undirected and directed graphs

Recently, Fredman and Tarjan invented a new, especially efficient form of heap (priority queue). Their data structure, theFibonacci heap (or F-heap) supports arbitrary deletion inO(logn) amortized time and other heap operations inO(1) amortized time. In this paper we use F-heaps to obtain fast algorithms for finding minimum spanning trees in undirected and directed graphs. For an undirected graph containingn vertices andm edges, our minimum spanning tree algorithm runs inO(m logβ (m, n)) time, improved fromO(mβ(m, n)) time, whereβ(m, n)=min {i|log⁽ⁱ⁾ n ≦m/n}. Our minimum spanning tree algorithm for directed graphs runs inO(n logn + m) time, improved fromO(n log n +m log log log_(m/n+2) n). Both algorithms can be extended to allow a degree constraint at one vertex. Research supported in part by National Science Foundation Grant MCS-8302648. Research supported in part by National Science Foundation Grant MCS-8303139. Research supported in part by National Science Foundation Grant MCS-8300984 and a United States Army Research Office Program Fellowship, DAAG29-83-GO020.     

Investigation of the interface in silica-encapsulated liposomes by combining solid state NMR and first principles calculations

In the context of nanomedicine, liposils (liposomes and silica) have a strong potential for drug storage and release schemes: such materials combine the intrinsic properties of liposome (encapsulation) and silica (increased rigidity, protective coating, pH degradability). In this work, an original approach combining solid state NMR, molecular dynamics, first principles geometry optimization, and NMR parameters calculation allows the building of a precise representation of the organic/inorganic interface in liposils. {(1)H-(29)Si}(1)H and {(1)H-(31)P}(1)H Double Cross-Polarization (CP) MAS NMR experiments were implemented in order to explore the proton chemical environments around the silica and the phospholipids, respectively. Using VASP (Vienna Ab Initio Simulation Package), DFT calculations including molecular dynamics, and geometry optimization lead to the determination of energetically favorable configurations of a DPPC (dipalmitoylphosphatidylcholine) headgroup adsorbed onto a hydroxylated silica surface that corresponds to a realistic model of an amorphous silica slab. These data combined with first principles NMR parameters calculations by GIPAW (Gauge Included Projected Augmented Wave) show that the phosphate moieties are not directly interacting with silanols. The stabilization of the interface is achieved through the presence of water molecules located in-between the head groups of the phospholipids and the silica surface forming an interfacial H-bonded water layer. A detailed study of the (31)P chemical shift anisotropy (CSA) parameters allows us to interpret the local dynamics of DPPC in liposils. Finally, the VASP/solid state NMR/GIPAW combined approach can be extended to a large variety of organic-inorganic hybrid interfaces.     

Polygon triangulation inO(n log logn) time with simple data structures

We give a newO(n log logn)-time deterministic algorithm for triangulating simplen-vertex polygons, which avoids the use of complicated data structures. In addition, for polygons whose vertices have integer coordinates of polynomially bounded size, the algorithm can be modified to run inO(n log*n) time. The major new techniques employed are the efficient location of horizontal visibility edges that partition the interior of the polygon into regions of approximately equal size, and a linear-time algorithm for obtaining the horizontal visibility partition of a subchain of a polygonal chain, from the horizontal visibility partition of the entire chain. The latter technique has other interesting applications, including a linear-time algorithm to convert a Steiner triangulation of a polygon into a true triangulation.This research was partially supported by the following grants: NSERC 583584, NSERC 580485, ONR-N00014-87-0467, and by DIMACS, an NSF Science and Technology Center (NSF-STC88-09648).     

Linear expected-time algorithms for connectivity problems

This paper describes fast average-time algorithms for four graph connectivity problems. Algorithms that run in O(n) average time on n-vertex graphs are developed for finding connected components, strong components, and blocks. An O(m)-time algorithm to find a minimum spanning forest in an m-graph is also presented. The analysis of these algorithms uses the random graph model of Erdös and Renyi. All the algorithms are optimum to within a constant factor.