More Like this

1. Graph Exploration by Energy-Sharing Mobile Agents

   Czyzowicz, J.; Dobrev, S.; Killick, R.; Kranakis, E.; Krizanc, D.; Narayanan, L.; Opatrny, J; Pankratov, D.; Shende, S. (July 2021, 28th International Colloquium on Structural Information and Communication Complexity (SIROCCO))

   null (Ed.)

   We consider the problem of collective exploration of a known n- node edge-weighted graph by k mobile agents that have limited energy but are capable of energy transfers. The agents are initially placed at an arbitrary subset of nodes in the graph, and each agent has an initial, possibly different, amount of energy. The goal of the exploration problem is for every edge in the graph to be traversed by at least one agent. The amount of energy used by an agent to travel distance x is proportional to x. In our model, the agents can share energy when co-located: when two agents meet, one can transfer part of its energy to the other. For an n-node path, we give an O(n+k) time algorithm that either nds an exploration strategy, or reports that one does not exist. For an n-node tree with l leaves, we give an O(n+lk^2) algorithm that finds an exploration strategy if one exists. Finally, for the general graph case, we show that the problem of deciding if exploration is possible by energy-sharing agents is NP-hard, even for 3-regular graphs. In addition, we show that it is always possible to find an exploration strategy if the total energy of the agents is at least twice the total weight of the edges; moreover, this is asymptotically optimal. 

   more » « less
2. Optimum UAV Positioning for Better Coverage-Connectivity Tradeoff

   Abdel-Malek, Mai; Ibrahim, Ahmed S.; Mokhtar, Mohamed (October 2017, IEEE International Symposium on Personal, Indoor, and Mobile Radio Communications (PIMRC'17))

   Unmanned aerial vehicle (UAV) plays prominent role in enhancing backhaul connectivity and providing extended coverage areas due to its mobility and flexible deployment. To realize these objectives simultaneously, we present a new framework for positioning the UAV to maximize the small-cells backhaul network connectivity characterized by its Fiedler value, the second smallest eigenvalue of the Laplacian matrix representing the network graph, while maintaining particular signal-to-noise ratio constraint for each individual user equipment. Moreover, we show that the localization problem can be approximated by a low complexity convex semi-definite programming optimization problem. Finally, our extensive simulations verify the approximation validity and demonstrate the potential gain of UAV deployment. 

   more » « less
3. The QuaSEFE Problem

   Angelini, P.; Forster, H.; Hoffmann, M.; Kaufmann, M.; Kobourov, S.; Liotta, G.; Patrigniani, M. (January 2019, International Symposium on Graph Drawing and Network Visualization)

   We initiate the study of Simultaneous Graph Embedding with Fixed Edges in the beyond planarity framework. In the QSEFE problem, we allow edge crossings, as long as each graph individually is drawn quasiplanar, that is, no three edges pairwise cross. %We call this problem the QSEFE problem. We show that a triple consisting of two planar graphs and a tree admit a QSEFE. This result also implies that a pair consisting of a 1-planar graph and a planar graph admits a QSEFE. We show several other positive results for triples of planar graphs, in which certain structural properties for their common subgraphs are fulfilled. For the case in which simplicity is also required, we give a triple consisting of two quasiplanar graphs and a star that does not admit a QSEFE. Moreover, in contrast to the planar SEFE problem, we show that it is not always possible to obtain a QSEFE for two matchings if the quasiplanar drawing of one matching is fixed. 

   more » « less
4. Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut

   https://doi.org/10.1145/3651148  

   Cheng, Yu; Li, Max; Lin, Honghao; Tai, Zi-Yi; Woodruff, David P.; Zhang, Jason (May 2024, Proceedings of the ACM on Management of Data)

   In this paper, we consider two fundamental cut approximation problems on large graphs. We prove new lower bounds for both problems that are optimal up to logarithmic factors. The first problem is approximating cuts in balanced directed graphs. In this problem, we want to build a data structure that can provide (1 ± ε)-approximation of cut values on a graph with n vertices. For arbitrary directed graphs, such a data structure requires Ω(n²) bits even for constant ε. To circumvent this, recent works study β-balanced graphs, meaning that for every directed cut, the total weight of edges in one direction is at most β times the total weight in the other direction. We consider the for-each model, where the goal is to approximate each cut with constant probability, and the for-all model, where all cuts must be preserved simultaneously. We improve the previous Ømega(n √β/ε) lower bound in the for-each model to ~Ω (n √β /ε) and we improve the previous Ω(n β/ε) lower bound in the for-all model to Ω(n β/ε²). This resolves the main open questions of (Cen et al., ICALP, 2021). The second problem is approximating the global minimum cut in a local query model, where we can only access the graph via degree, edge, and adjacency queries. We prove an ΩL(min m, m/ε²k R) lower bound for this problem, which improves the previous ΩL(m/k R) lower bound, where m is the number of edges, k is the minimum cut size, and we seek a (1+ε)-approximation. In addition, we show that existing upper bounds with minor modifications match our lower bound up to logarithmic factors. 

   more » « less
5. Line Coverage with Multiple Robots

   https://doi.org/10.1109/ICRA40945.2020.9197292  

   Agarwal, Saurav; Akella, Srinivas (June 2020, IEEE International Conference on Robotics and Automation)

   The line coverage problem is the coverage of linear environment features (e.g., road networks, power lines), modeled as 1D segments, by one or more robots while respecting resource constraints (e.g., battery capacity, flight time) for each of the robots. The robots incur direction dependent costs and resource demands as they traverse the edges. We treat the line coverage problem as an optimization problem, with the total cost of the tours as the objective, by formulating it as a mixed integer linear program (MILP). The line coverage problem is NP-hard and hence we develop a heuristic algorithm, Merge- Embed-Merge (MEM). We compare it against the optimal MILP approach and a baseline heuristic algorithm, Extended Path Scanning. We show the MEM algorithm is fast and suitable for real-time applications. To tackle large-scale problems, our approach performs graph simplification and graph partitioning, followed by robot tour generation for each of the partitioned subgraphs. We demonstrate our approach on a large graph with 4,658 edges and 4,504 vertices that represents an urban region of about 16 sq. km. We compare the performance of the algorithms on several small road networks and experimentally demonstrate the approach using UAVs on the UNC Charlotte campus road network. 

   more » « less