BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
We present a new algorithm for maintaining a DFS tree of an arbitrary directed graph under any sequence of edge insertions. Our algorithm requires a total of O(m⋅n) time in the worst case to process a sequence of edge insertions, where n is the number of vertices in the graph and m is the total number of edges in the final graph. We also prove lower bounds for variations of this problem.
In this paper we present an efficient reachability oracle under single-edge or single-vertex failures for planar directed graphs. Specifically, we show that a planar digraph G can be preprocessed in O(nlog2n/loglogn) time, producing an O(nlogn)-space data structure that can answer in O(logn) time whether u can reach v in G if the vertex x (the edge~f) is removed from G, for any query vertices u,v and failed vertex x (failed edge f). To the best of our knowledge, this is the first data structure for planar directed graphs with nearly optimal preprocessing time that answers all-pairs queries under any kind of failures in polylogarithmic time. We also consider 2-reachability problems, where we are given a planar digraph G and we wish to determine if there are two vertex-disjoint (edge-disjoint) paths from u to v, for query vertices u,v. In this setting we provide a nearly optimal 2-reachability oracle, which is the existential variant of the reachability oracle under single failures, with the following bounds. We can construct in O(nlogO(1)n) time an O(nlog3+o(1)n)-space data structure that can check in O(log2+o(1)n) time for any query vertices u,v whether v is 2-reachable from u, or otherwise find some separating vertex (edge) x lying on all paths from u to v in G. To obtain our results, we follow the general recursive approach of Thorup for reachability in planar graphs [J.~ACM~'04] and we present new data structures which generalize dominator trees and previous data structures for strong-connectivity under failures [Georgiadis et al., SODA~'17]. Our new data structures work also for general digraphs and may be of independent interest.
Motivated by recent applications of dominator computations, we consider the problem of dynamically maintaining the dominators of flow graphs through a sequence of insertions and deletions of edges. Our main theoretical contribution is a simple incremental algorithm that maintains the dominator tree of a flow graph with n vertices through a sequence of k edge insertions in O(mmin{n,k}+kn) time, where m is the total number of edges after all insertions. Moreover, we can test in constant time if a vertex u dominates a vertex v, for any pair of query vertices u and v. Next, we present a new decremental algorithm to update a dominator tree through a sequence of edge deletions. Although our new decremental algorithm is not asymptotically faster than repeated applications of a static algorithm, i.e., it runs in O(mk) time for k edge deletions, it performs well in practice. By combining our new incremental and decremental algorithms we obtain a fully dynamic algorithm that maintains the dominator tree through intermixed sequence of insertions and deletions of edges. Finally, we present efficient implementations of our new algorithms as well as of existing algorithms, and conduct an extensive experimental study on real-world graphs taken from a variety of application areas.
We develop a dynamic version of the primal-dual method for optimization problems, and apply it to obtain the following results. (1) For the dynamic set-cover problem, we maintain an O(f2)-approximately optimal solution in O(f⋅log(m+n)) amortized update time, where f is the maximum "frequency" of an element, n is the number of sets, and m is the maximum number of elements in the universe at any point in time. (2) For the dynamic b-matching problem, we maintain an O(1)-approximately optimal solution in O(log3n) amortized update time, where n is the number of nodes in the graph.
In this paper, we initiate the study of the dynamic maintenance of 2-edge-connectivity relationships in directed graphs. We present an algorithm that can update the 2-edge-connected blocks of a directed graph with n vertices through a sequence of m edge insertions in a total of O(mn) time. After each insertion, we can answer the following queries in asymptotically optimal time: (i) Test in constant time if two query vertices v and w are 2-edge-connected. Moreover, if v and w are not 2-edge-connected, we can produce in constant time a "witness" of this property, by exhibiting an edge that is contained in all paths from v to w or in all paths from w to v. (ii) Report in O(n) time all the 2-edge-connected blocks of G. To the best of our knowledge, this is the first dynamic algorithm for 2-connectivity problems on directed graphs, and it matches the best known bounds for simpler problems, such as incremental transitive closure.
Let G be a strongly connected directed graph. We consider the following three problems, where we wish to compute the smallest strongly connected spanning subgraph of G that maintains respectively: the 2-edge-connected blocks of G (\textsf{2EC-B}); the 2-edge-connected components of G (\textsf{2EC-C}); both the 2-edge-connected blocks and the 2-edge-connected components of G (\textsf{2EC-B-C}). All three problems are NP-hard, and thus we are interested in efficient approximation algorithms. For \textsf{2EC-C} we can obtain a 3/2-approximation by combining previously known results. For \textsf{2EC-B} and \textsf{2EC-B-C}, we present new 4-approximation algorithms that run in linear time. We also propose various heuristics to improve the size of the computed subgraphs in practice, and conduct a thorough experimental study to assess their merits in practical scenarios.
Edge and vertex connectivity are fundamental concepts in graph theory. While they have been thoroughly studied in the case of undirected graphs, surprisingly not much has been investigated for directed graphs. In this paper we study 2-edge connectivity problems in directed graphs and, in particular, we consider the computation of the following natural relation: We say that two vertices v and w are 2-edge-connected if there are two edge-disjoint paths from v to w and two edge-disjoint paths from w to v. This relation partitions the vertices into blocks such that all vertices in the same block are 2-edge-connected. Differently from the undirected case, those blocks do not correspond to the 2-edge-connected components of the graph. We show how to compute this relation in linear time so that we can report in constant time if two vertices are 2-edge-connected. We also show how to compute in linear time a sparse certificate for this relation, i.e., a subgraph of the input graph that has O(n) edges and maintains the same 2-edge-connected blocks as the input graph.
We present the first deterministic data structures for maintaining approximate minimum vertex cover and maximum matching in a fully dynamic graph G=(V,E), with ∣V∣=n and ∣E∣=m, in o(m) time per update. In particular, for minimum vertex cover we provide deterministic data structures for maintaining a $(2+\eps)$ approximation in $O(\log n/\eps^2)$ amortized time per update. For maximum matching, we show how to maintain a $(3+\eps)$ approximation in $O(\min(\sqrt{n}/ε, m^{1/3}/\eps^2))$ {\em amortized} time per update, and a $(4+\eps)$ approximation in $O(m^{1/3}/\eps^2)$ {\em worst-case} time per update. Our data structure for fully dynamic minimum vertex cover is essentially near-optimal and settles an open problem by Onak and Rubinfeld from STOC' 2010.
In this paper, we describe the result of our experiments on Algorithms for the Food-Selection Problem, which is the fundamental problem first stated and addressed in the seminal paper \cite{pigout}. Because the key aspect of any experimental evaluation is the \textbf{reproducibility}, we detail deeply the setup of all our experiments, thus leaving to the interested eater the opportunity to reproduce all the results described in this paper. More specifically, we describe all the answers we provided to the questions proposed in \cite{pigout}: Where can I have dinner tonight? What is the typical Roman cuisine that I should (not) miss? Where can I find the best coffee or gelato in town?
Every time the customer (individual or company) has to release personal information to its service provider (e.g., an online store or a cloud computing provider), it faces a trade-off between the benefits gained (enhanced or cheaper services) and the risks it incurs (identity theft and fraudulent uses). The amount of personal information released is the major decision variable in that trade-off problem, and has a proxy in the maximum loss the customer may incur. We find the conditions for a unique optimal solution to exist for that problem as that maximizing the customer's surplus. We also show that the optimal amount of personal information is influenced most by the immediate benefits the customer gets, i.e., the price and the quantity of service offered by the service provider, rather than by maximum loss it may incur. Easy spenders take larger risks with respect to low-spenders, but an increase in price drives customers towards a more careful risk-taking attitude anyway. A major role is also played by the privacy level, which the service provider employs to regulate the benefits released to the customers. We also provide a closed form solution for the limit case of a perfectly secure provider, showing that the results do not differ significantly from those obtained in the general case. The trade-off analysis may be employed by the customer to determine its level of exposure in the relationship with its service provider.
In this paper we study minimum cut and maximum flow problems on planar graphs, both in static and in dynamic settings. First, we present an algorithm that given an undirected planar graph computes the minimum cut between any two given vertices in O(n log log n) time. Second, we show how to achieve the same O(n log log n) bound for the problem of computing maximum flows in undirected planar graphs. To the best of our knowledge, these are the first algorithms for those two problems that break the O(n log n) barrier, which has been standing for more than 25 years. Third, we present a fully dynamic algorithm that is able to maintain information about minimum cuts and maximum flows in a plane graph (i.e., a planar graph with a fixed embedding): our algorithm is able to insert edges, delete edges and answer min-cut and max-flow queries between any pair of vertices in O(n^(2/3) log^3 n) time per operation. This result is based on a new dynamic shortest path algorithm for planar graphs which may be of independent interest. We remark that this is the first known non-trivial algorithm for min-cut and max-flow problems in a dynamic setting.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.