1,720,991 research outputs found
Almost optimal algorithms for diameter-optimally augmenting trees
No full textWe consider the problem of augmenting an n-vertex tree with one shortcut in order to minimize the diameter of the resulting graph. The tree is embedded in an unknown space and we have access to an oracle that, when queried on a pair of vertices u and v, reports the weight of the shortcut (u,v) in constant time. Previously, the problem was solved in O(n2log3n) time for general weights [Oh and Ahn, ISAAC 2016], in O(n2logn) time for trees embedded in a metric space [Große et al., Int. J. FCS], and in O(nlogn) time for paths embedded in a metric space [Wang, Comput. Geom.]. Very recently an algorithm for general weights requiring O(n2logn) time and O(n) space has been developed [Wang and Zhao, Theor. Comp. Science]. Finally, a (1+ε)-approximation algorithm running in O(n+1/ε3) has been designed for paths embedded in Rd, for constant values of d [Große et al., Int. J. FCS]. In this paper we design an asymptotic time-optimal algorithm for trees and general edge-weights that requires O(n2) time and O(nlogn) space. Moreover, for trees embedded in a metric space, we design (i) an exact O(nlogn)-time algorithm and (ii) a (1+ε)-approximation algorithm that runs in O(n+ε−1logε−1) time
Blackout-Tolerant Temporal Spanners
No full textIn this paper we introduce the notions of blackout-tolerant temporal -spanner of a temporal graph G which is a subgraph of G that preserves the distances between pairs of vertices of interest in G up to a multiplicative factor of, even when the graph edges at a single time-instant become unavailable. In particular, we consider the single-source, single-pair, and all-pairs cases and, for each case we look at three quality requirements: exact distances (i.e.,), almost-exact distances (i.e., for an arbitrarily small constant), and connectivity (i.e., unbounded). For each combination we provide tight bounds, up to polylogarithmic factors, on the size, which is measured as the number of edges, of the corresponding blackout-tolerant-spanner for both general temporal graphs and for temporal cliques. Our result show that such spanners are either very sparse (i.e., they have edges) or they must have size in the worst case, where n is the number of vertices of G. To complete the picture, we also investigate the case of multiple blackouts
Sparse Temporal Spanners with Low Stretch
Full text linkA temporal graph is an undirected graph G = (V,E) along with a function λ : E → N+ that assigns a time-label to each edge in E. A path in G such that the traversed time-labels are non-decreasing is called a temporal path. Accordingly, the distance from u to v is the minimum length (i.e., the number of edges) of a temporal path from u to v. A temporal α-spanner of G is a (temporal) subgraph H that preserves the distances between any pair of vertices in V , up to a multiplicative stretch factor of α. The size of H is measured as the number of its edges. In this work, we study the size-stretch trade-offs of temporal spanners. In particular we show that temporal cliques always admit a temporal (2k -1)-spanner with eO(kn1+1k ) edges, where k > 1 is an integer parameter of choice. Choosing k = log n⌉, we obtain a temporal O(log n)-spanner with eO(n) edges that has almost the same size (up to logarithmic factors) as the temporal spanner given in [Casteigts et al., JCSS 2021] which only preserves temporal connectivity. We then turn our attention to general temporal graphs. Since Ω(n2) edges might be needed by any connectivity-preserving temporal subgraph [Axiotis et al., ICALP'16], we focus on approximating distances from a single source. We show that eO(n/ log(1 + ε)) edges suffice to obtain a stretch of (1 + ε), for any small ε > 0. This result is essentially tight in the following sense: There are temporal graphs G for which any temporal subgraph preserving exact distances from a single-source must use Ω(n2) edges. Interestingly enough, our analysis can be extended to the case of additive stretch for which we prove an upper bound of eO(n2/β) on the size of any temporal β-additive spanner, which we show to be tight up to polylogarithmic factors. Finally, we investigate how the lifetime of G, i.e., the number of its distinct time-labels, affects the trade-off between the size and the stretch of a temporal spanner
An Improved Algorithm for Computing All the Best Swap Edges of a Tree Spanner
No full textA tree σ -spanner of a positively real-weighted n-vertex and m-edge undirected graph G is a spanning tree T of G which approximately preserves (i.e., up to a multiplicative stretch factor σ ) distances in G. Tree spanners with provably good stretch factors find applications in communication networks, distributed systems, and network design. However, finding an optimal or even a good tree spanner is a very hard computational task. Thus, if one has to face a transient edge failure in T, the overall effort that has to be afforded to rebuild a new tree spanner (i.e., computational costs, set-up of new links, updating of the routing tables, etc.) can be rather prohibitive. To circumvent this drawback, an effective alternative is that of associating with each tree edge a best possible (in terms of resulting stretch) swap edge—a well-established approach in the literature for several other tree topologies. Correspondingly, the problem of computing all the best swap edges of a tree spanner is a challenging algorithmic problem, since solving it efficiently means to exploit the structure of shortest paths not only in G, but also in all the scenarios in which an edge of T has failed. For this problem we provide a very efficient solution, running in O(n2log4n) time, which drastically improves (almost by a quadratic factor in n in dense graphs) on the previous known best result
Deterministic Sensitivity Oracles for Diameter, Eccentricities and All Pairs Distances
Full text linkWe construct data structures for extremal and pairwise distances in directed graphs in the presence of transient edge failures. Henzinger et al. [ITCS 2017] initiated the study of fault-tolerant (sensitivity) oracles for the diameter and vertex eccentricities. We extend this with a special focus on space efficiency. We present several new data structures, among them the first fault-tolerant eccentricity oracle for dual failures in subcubic space. We further prove lower bounds that show limits to approximation vs. space and diameter vs. space trade-offs for fault-tolerant oracles. They highlight key differences between data structures for undirected and directed graphs. Initially, our oracles are randomized leaning on a sampling technique frequently used in sensitivity analysis. Building on the work of Alon, Chechik, and Cohen [ICALP 2019] as well as Karthik and Parter [SODA 2021], we develop a hierarchical framework to derandomize fault-tolerant data structures. We first apply it to our own diameter and eccentricity oracles and then show its versatility by derandomizing algorithms from the literature: the distance sensitivity oracle of Ren [JCSS 2022] and the Single-Source Replacement Path algorithm of Chechik and Magen [ICALP 2020]. This way, we obtain the first deterministic distance sensitivity oracle with subcubic preprocessing time
Geometric Network Creation Games
No full textNetwork creation games are a well-known approach for explaining and analyzing the structure, quality, and dynamics of real-world networks that evolved via the interaction of selfish agents without a central authority. In these games selfish agents corresponding to nodes in a network strategically buy incident edges to improve their centrality. However, past research on these games only considered the creation of networks with unit-weight edges. In practice, e.g., when constructing a fiber-optic network, the choice of which nodes to connect and also the induced price for a link crucially depend on the distance between the involved nodes, and such settings can be modeled via edge-weighted graphs. We incorporate arbitrary edge weights by generalizing the well-known model by Fabrikant et al. [Proceedings of PODC'03, ACM, 2003, pp. 347-351] to edge-weighted host graphs and focus on the geometric setting where the weights are induced by the distances in some metric space. In stark contrast to the state of the art for the unit-weight version, where the price of anarchy is conjectured to be constant and where resolving this is a major open problem, we prove a tight nonconstant bound on the price of anarchy for the metric version and a slightly weaker upper bound for the nonmetric case. Moreover, we analyze the existence of equilibria, the computational hardness, and the game dynamics for several natural metrics. The model we propose can be seen as the game-theoretic analogue of the classical network design problem. Thus, low-cost equilibria of our game correspond to decentralized and stable approximations of the optimum network design
Tolerance is Necessary for Stability: Single-Peaked Swap Schelling Games
Full text linkResidential segregation in metropolitan areas is a phenomenon that can be observed all over the world. Recently, this was investigated via game-theoretic models. There, selfish agents of two types are equipped with a monotone utility function that ensures higher utility if an agent has more same-type neighbors. The agents strategically choose their location on a given graph that serves as residential area to maximize their utility. However, sociological polls suggest that real-world agents are actually favoring mixed-type neighborhoods, and hence should be modeled via non-monotone utility functions. To address this, we study Swap Schelling Games with single-peaked utility functions. Our main finding is that tolerance, i.e., agents favoring fifty-fifty neighborhoods or being in the minority, is necessary for equilibrium existence on almost regular or bipartite graphs. Regarding the quality of equilibria, we derive (almost) tight bounds on the Price of Anarchy and the Price of Stability. In particular, we show that the latter is constant on bipartite and almost regular graphs
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
- …
