Zobrazeno 1 - 10
of 98
pro vyhledávání: '"Baswana, Surender"'
Autor:
Baswana, Surender, Bhanja, Koustav
Let G be a directed weighted graph (DiGraph) on n vertices and m edges with source s and sink 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, a long line of work has been don
Externí odkaz:
http://arxiv.org/abs/2310.12096
Autor:
Baswana, Surender, Pandey, Abhyuday
Let $G=(V,E)$ be an undirected unweighted graph on $n$ vertices and $m$ edges. We address the problem of sensitivity oracle for all-pairs mincuts in $G$ defined as follows. Build a compact data structure that, on receiving any pair of vertices $s,t\i
Externí odkaz:
http://arxiv.org/abs/2011.03291
Autor:
Baswana, Surender, Chakrabarti, Partha Pratim, Kanoria, Yashodhan, Patange, Utkarsh, Chandran, Sharat
Until 2014, admissions to the Indian Institutes of Technology (IITs) were conducted under one umbrella, whereas the admissions to the non-IIT Centrally Funded Government Institutes (CFTIs) were conducted under a different umbrella, the Central Seat A
Externí odkaz:
http://arxiv.org/abs/1904.06698
We present an algorithm for a fault tolerant Depth First Search (DFS) Tree in an undirected graph. This algorithm is drastically simpler than the current state-of-the-art algorithms for this problem, uses optimal space and optimal preprocessing time,
Externí odkaz:
http://arxiv.org/abs/1810.01726
Depth First Search (DFS) tree is a fundamental data structure for solving graph problems. The DFS tree of a graph $G$ with $n$ vertices and $m$ edges can be built in $O(m+n)$ time. Till date, only a few algorithms have been designed for maintaining i
Externí odkaz:
http://arxiv.org/abs/1705.02613
In this paper we study the problem of maintaining the strongly connected components of a graph in the presence of failures. In particular, we show that given a directed graph $G=(V,E)$ with $n=|V|$ and $m=|E|$, and an integer value $k\geq 1$, there i
Externí odkaz:
http://arxiv.org/abs/1610.04010
Depth first search (DFS) tree is a fundamental data structure for solving various problems in graphs. It is well known that it takes $O(m+n)$ time to build a DFS tree for a given undirected graph $G=(V,E)$ on $n$ vertices and $m$ edges. We address th
Externí odkaz:
http://arxiv.org/abs/1502.02481
We present a fully dynamic algorithm for maintaining approximate maximum weight matching in general weighted graphs. The algorithm maintains a matching ${\cal M}$ whose weight is at least $1/8 M^{*}$ where $M^{*}$ is the weight of the maximum weight
Externí odkaz:
http://arxiv.org/abs/1207.3976
We present an algorithm for maintaining maximal matching in a graph under addition and deletion of edges. Our data structure is randomized that takes O(log n) expected amortized time for each edge update where n is the number of vertices in the graph
Externí odkaz:
http://arxiv.org/abs/1103.1109
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.