Search for: All records

We show the first near-linear time randomized algorithms for listing all minimum vertex cuts of polylogarithmic size that separate the graph into at least three connected components (also known as shredders) and for finding the most shattering one, i.e., the one maximizing the number of connected components. Our algorithms break the quadratic time bound by Cheriyan and Thurimella (STOC'96) for both problems that has been unimproved for more than two decades. Our work also removes an important bottleneck to near-linear time algorithms for the vertex connectivity augmentation problem (Jordan '95) and finding an even-length directed cycle in a graph, a problem shown to be equivalent to many other fundamental problems (Vazirani and Yannakakis '90, Robertson et al. '99). Note that it is necessary to list only minimum vertex cuts that separate the graph into at least three components because there can be an exponential number of minimum vertex cuts in general. To obtain a near-linear time algorithm, we have extended techniques in local flow algorithms developed by Forster et al. (SODA'20) to list shredders on a local scale. We also exploit fast queries to a pairwise vertex connectivity oracle subject to vertex failures (Long and Saranurak FOCS'22, Kosinas ESA'23). This is the first application of using connectivity oracles subject to vertex failures to speed up a static graph algorithm. 

Pistons are ubiquitous devices used for fluid-mechanical energy conversion. However, despite this ubiquity and centuries of development, the forces and motions produced by conventional rigid pistons are limited by their design. The use of flexible materials and structures opens a door to the design of a piston with unconventional features. In this study, an architecture for pistons that utilizes a combination of flexible membrane materials and compressible rigid structures is proposed. In contrast to conventional pistons, the fluid- pressure-induced tension forces in the flexible membrane play a primary role in the system, rather than compressive forces on the internal surfaces of the piston. The compressive skeletal structures offer the opportunity for the production of tunable forces and motions in the “tension piston” system. The experimental results indicate that the tension piston concept is able to produce substantially greater force (more than three times), higher power, and higher energy efficiency (more than 40% improvement at low pressures) compared to a conventional piston, and these features enable myriad potential applications for the tension piston as a drop-in replacement for existing pistons.