244 research outputs found
Minimum+1 Steiner Cut and Dual Edge Sensitivity Oracle: Bridging Gap between Global and (s,t)-cut
No full textLet G = (V,E) be an undirected multi-graph on n = |V| vertices and S ⊆ V be a Steiner set in G. Steiner cut is a fundamental concept; moreover, global cut (|S| = n), as well as (s,t)-cut (|S| = 2), is just a special case of Steiner cut. We study Steiner cuts of capacity minimum+1, and as an important application, we provide a dual edge Sensitivity Oracle for Steiner mincut - a compact data structure for efficiently reporting a Steiner mincut after failure/insertion of any pair of edges.
A compact data structure for cuts of capacity minimum+1 has been designed for both global cuts [Dinitz and Nutov, STOC 1995] and (s,t)-cuts [Baswana, Bhanja, and Pandey, ICALP 2022 & TALG 2023]. Moreover, both data structures are also used crucially to design a dual edge Sensitivity Oracle for their respective mincuts. Unfortunately, except for these two extreme scenarios of Steiner cuts, no generalization of these results is known. Therefore, to address this gap, we present the following first results on Steiner cuts for any S satisfying 2 ≤ |S| ≤ n.
1) Data Structure for Minimum+1 Steiner Cut: There is an {O}(n(n-|S|+1)) space data structure that, given any pair of vertices u,v, can determine in {O}(1) time whether the Steiner cut of the least capacity separating u and v has capacity minimum+1. It can report such a cut, if it exists, in {O}(n) time, which is worst-case optimal.
2) Dual Edge Sensitivity Oracle: We design the following pair of data structures. (a) There is an {O}(n(n-|S|+1)) space data structure that, after the failure or insertion of any pair of edges in G, can report the capacity of Steiner mincut in {O}(1) time and a Steiner mincut in {O}(n) time, which is worst-case optimal. (b) If we are interested in reporting only the capacity of Steiner mincut, there is a more compact data structure that occupies {O}((n-|S|)²+n) space and can report the capacity of Steiner mincut in {O}(1) time after the failure or insertion of any pair of edges.
3) Lower Bound for Sensitivity Oracle: For undirected multi-graphs, for any Steiner set S ⊆ V, any data structure that, after the failure or insertion of any pair of edges, can report the capacity of Steiner mincut must occupy Ω((n-|S|)²) bits of space in the worst case, irrespective of the query time. To arrive at our results, we provide several techniques, especially a generalization of the 3-Star Lemma given by Dinitz and Vainshtein [SICOMP 2000], which is of independent interest.
Our results achieve the same space and time bounds of the existing results for the two extreme scenarios of Steiner cuts - global and (s,t)-cut. In addition, the space occupied by our data structures in (1) and (2) reduces as |S| tends to n. Also, they occupy subquadratic space if |S| is close to n
Vital Edges for (s,t)-Mincut: Efficient Algorithms, Compact Structures, & Optimal Sensitivity Oracles
No full textLet G be a directed weighted graph on n vertices and m edges with designated source and sink vertices s and t. An edge in G is vital if its removal reduces the capacity of (s,t)-mincut. Since the seminal work of Ford and Fulkerson [CJM 1956], a long line of work has been done on computing the most vital edge and all vital edges of G. However, even after 60 years, the existing results are for either undirected or unweighted graphs. We present the following result for directed weighted graphs that also solves an open problem by Ausiello, Franciosa, Lari, and Ribichini [NETWORKS 2019].
1. Algorithmic Results: There is an algorithm that computes all vital edges as well as the most vital edge of G using {O}(n) maximum (s,t)-flow computations.
Vital edges play a crucial role in the design of sensitivity oracle for (s,t)-mincut - a compact data structure for reporting (s,t)-mincut after insertion/failure of any edge. For directed graphs, the only existing sensitivity oracle is for unweighted graphs by Picard and Queyranne [MPS 1982]. We present the first and optimal sensitivity oracle for directed weighted graphs as follows.
2. Sensitivity Oracles:
a) There is an optimal O(n²) space data structure that can report an (s,t)-mincut C in O(|C|) time after the failure/insertion of any edge.
b) There is an O(n) space data structure that can report the capacity of (s,t)-mincut after failure or insertion of any edge e in O(1) time if the capacity of edge e is known.
A mincut for a vital edge e is an (s,t)-cut of the least capacity in which edge e is outgoing. For unweighted graphs, in a classical work, Picard and Queyranne [MPS 1982] designed an O(m) space directed acyclic graph (DAG) that stores and characterizes all mincuts for all vital edges. Conversely, there is a set containing at most n-1 (s,t)-cuts such that at least one mincut for every vital edge belongs to the set. We generalize these results for directed weighted graphs as follows.
3. Structural & Combinatorial Results:
a) There is a set M containing at most n-1 (s,t)-cuts such that at least one mincut for every vital edge belongs to the set. This bound is tight as well. We also show that set M can be computed using O(n) maximum (s,t)-flow computations.
b) We design two compact structures for storing and characterizing all mincuts for all vital edges - (i) an O(m) space DAG for partial and (ii) an O(mn) space structure for complete characterization.
To arrive at our results, we develop new techniques, especially a generalization of maxflow-mincut Theorem by Ford and Fulkerson [CJM 1956], which might be of independent interest
Optimal Sensitivity Oracle for Steiner Mincut
No full textLet G = (V,E) be an undirected weighted graph on n = |V| vertices and S ⊆ V be a Steiner set. Steiner mincut is a well-studied concept, which also provides a generalization to both (s,t)-mincut (when |S| = 2) and global mincut (when |S| = n). Here, we address the problem of designing a compact data structure that can efficiently report a Steiner mincut and its capacity after the failure of any edge in G; such a data structure is known as a Sensitivity Oracle for Steiner mincut.
In the area of minimum cuts, although many Sensitivity Oracles have been designed in unweighted graphs, however, in weighted graphs, Sensitivity Oracles exist only for (s,t)-mincut [Annals of Operations Research 1991, NETWORKS 2019, ICALP 2024], which is just a special case of Steiner mincut. Here, we generalize this result from |S| = 2 to any arbitrary set S ⊆ V, that is, 2 ≤ |S| ≤ n.
We first design an {O}(n²) space Sensitivity Oracle for Steiner mincut by suitably generalizing the approach used for (s,t)-mincuts [Annals of Operations Research 1991, NETWORKS 2019]. However, the main question that arises quite naturally is the following.
Can we design a Sensitivity Oracle for Steiner mincut that breaks the {O}(n²) bound on space?
In this article, we present the following two results that provide an answer to this question.
1. Sensitivity Oracle: Assuming the capacity of every edge is known,
a) there is an O(n) space data structure that can report the capacity of Steiner mincut in O(1) time and
b) there is an O(n(n-|S|+1)) space data structure that can report a Steiner mincut in O(n) time after the failure of any edge in G.
2. Lower Bound: We show that any data structure that, after the failure of any edge in G, can report a Steiner mincut or its capacity must occupy Ω(n²) bits of space in the worst case, irrespective of the size of the Steiner set.
The lower bound in (2) shows that the assumption in (1) is essential to break the Ω(n²) lower bound on space. Sensitivity Oracle in (1.b) occupies only subquadratic, that is O(n^{1+ε}), space if |S| = n-n^ε+1, for every ε ∈ [0,1). For |S| = n-k for any constant k ≥ 0, it occupies only O(n) space. So, we also present the first Sensitivity Oracle occupying O(n) space for global mincut. In addition, we are able to match the existing best-known bounds on both space and query time for (s,t)-mincut [Annals of Operations Research 1991, NETWORKS 2019] in undirected graphs
Genetic characterization of Bhanja virus and Palma virus, two tick-borne phleboviruses
No full textThe genomes of Bhanja virus (BHAV) and Palma virus (PALV) two tick-borne viruses hitherto grouped into the Bhanja virus antigenic complex of the Bunyaviridae were determined by pyrosequencing. Phylogenetic analysis groups all three segments of BHAV and PALV into a distinct clade of tick-borne phleboviruses together with the newly described severe fever with thrombocytopenia syndrome virus and Uukuniemi virus. The terminal signature sequences which are signatures for taxonomic grouping and important for virus replication and RNA transcription show marked differences in the L- and S-segments
Minimum+1 (s,t)-cuts and Dual Edge Sensitivity Oracle
No full textLet G be a directed multi-graph on n vertices and m edges with a designated source vertex s and a designated sink vertex t. We study the (s,t)-cuts of capacity minimum+1 and as an important application of them, we give a solution to the dual edge sensitivity for (s,t)-mincuts - reporting the (s,t)-mincut upon failure or addition of any pair of edges.
Picard and Queyranne [Mathematical Programming Studies, 13(1):8-16, 1980] showed that there exists a directed acyclic graph (DAG) that compactly stores all minimum (s,t)-cuts of G. This structure also acts as an oracle for the single edge sensitivity of minimum (s,t)-cut. Dinitz and Nutov [STOC, pages 509-518, 1995] showed that there exists an (n) size 2-level cactus model that stores all global cuts of capacity minimum+1. However, for minimum+1 (s,t)-cuts, no such compact structures exist till date. We present the following structural and algorithmic results on minimum+1 (s,t)-cuts.
1) There exists a pair of DAGs of size O(m) that compactly store all minimum+1 (s,t)-cuts of G. Each minimum+1 (s,t)-cut appears as a (s,t)-cut in one of the 2 DAGs and is 3-transversal - it intersects any path in the DAG at most thrice.
2) There exists an O(n²) size data structure that, given a pair of vertices {u,v} which are not separated by an (s,t)-mincut, can determine in (1) time if there exists a minimum+1 (s,t)-cut, say (A,B), such that {s,u} ∈ A and {v,t} ∈ B; the corresponding cut can be reported in (|B|) time.
3) There exists an O(n²) size data structure that solves the dual edge sensitivity problem for (s,t)-mincuts. It takes (1) time to report the value of a resulting (s,t)-mincut (A,B) and (|B|) time to report the cut.
4) For the data structure problems addressed in (2) and (3) above, we also provide a matching conditional lower bound. We establish a close relationship among three seemingly unrelated problems – all-pairs directed reachability problem, the dual edge sensitivity problem for (s,t)-mincuts, and 2× 2 maximum flow. Assuming the directed reachability hypothesis, this leads to Ω(n²) lower bounds on the space for the latter two problems
QCA Circuits for Robust Coplanar Crossing
No full textIn this paper, different circuits of Quantum-dot Cellular Automata (QCA) are proposed for the so-called coplanar crossing. Coplanar crossing is one of the most interesting features of QCA because it allows for mono-layered interconnected circuits, whereas CMOS technology needs different levels of metalization. However, the characteristics of the coplanar crossing make it prone to malfunction due to thermal noise or defects. The proposed circuits exploit the majority voting properties of QCA to allow a robust crossing of wires on the Cartesian plane. This is accomplished using enlarged lines and voting. A Bayesian Network (BN) based simulator is utilized for evaluation; results are provided to assess robustness in the presence of cell defects and thermal effects. The BN simulator provides fast and reliable computation of the signal polarization versus normalized temperature. Simulation of the wire crossing circuits at different operating temperatures is provided with respect to defects and a quantitative metric for performance under temperature variations is proposed and assessed. I
Design of NML Circuits based on M-RAM
No full textNanoMagnet Logic (NML) is an emerging technol- ogy that allows to design digital circuits using nanomagnets. Each magnet has only two possible states and encodes digital informa- tion without the need for currents or voltages. This behavior differentiates NML circuits from charge based technologies. The advantages provided by NML circuits are a possible very low power consumption, and the ability to mix logic and memory in the same device. While a rich experimental activity on NML circuits can be found in literature, the feasibility of a complete NML system remains to be demonstrated yet. In this work we explore the possibility of implementing NML logic circuits based on the physical structure of Magnetic RAM (M-RAM). The advantages are twofold: First, M-RAM is a well developed technology, ready for the commercial stage, second it intrinsically provides an interface toward the CMOS world. To demonstrate the feasibility of NML circuits based on M-RAM we have designed a 3-input Ex-OR gate, using two different physical layouts for control signals. The first solution is strictly based on the M-RAM structure; the second solution requires a more complex fabrication process but leads to a smaller area. Circuits are simulated using VHDL language, with the aid of a tool that we have developed which automatically generates the VHDL code starting from the circuit layout. Overall, the solution here presented is a considerable step-forward toward the development of a complete magnetic circui
Novel designs for thermally robust coplanar crossing in QCA
No full textIn this paper, different circuit arrangements of Quantum-dot Cellular Automata (QCA) are proposed for the so-called coplanar crossing. These arrangements exploit the major-ity voting properties of QCA to allow a robust crossing of wires on the Cartesian plane. This is accomplished using enlarged lines and voting. Using a Bayesian Network (BN) based simulator, new results are provided to evaluate the robustness to so-called kink of these arrangements to ther-mal variations. The BN simulator provides fast and reli-able computation of the signal polarization versus normal-ized temperature. It is shown that by modifying the layout, a higher polarization level can be achieved in the routed sig-nal by utilizing the proposed QCA arrangements. 1
Sublethal effects of pesticide on selected stored product insect.
No full textThis Dissertation / Report is the outcome of investigation carried out by the creator(s) / author(s) at the department/division of Central Food Technological Research Institute (CFTRI), Mysore mentioned below in this page
- …
