52 Search Results for "Zhu, Di"

Document
DOI: 10.4230/LIPIcs.CPM.2026.13
Totally Unclustered BWT Images of Any Length over Non-Binary Alphabets

Authors: Gabriele Fici, Estéban Gabory, Giuseppe Romana, and Marinella Sciortino

Published in: LIPIcs, Volume 369, 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)

Abstract
We prove that for every integer n > 0 and for every alphabet Σ_k of size k ≥ 3, there exist words of length n whose Burrows-Wheeler Transform (BWT) is totally unclustered, i.e., it consists of exactly n runs with no two consecutive equal symbols. These words represent the worst-case behavior of the clustering effect of the BWT. We also establish a lower bound on their number. This contrasts with the binary case, where the existence of infinitely many totally unclustered BWT images is still an open problem, related to Artin’s conjecture on primitive roots.
Cite as

Gabriele Fici, Estéban Gabory, Giuseppe Romana, and Marinella Sciortino. Totally Unclustered BWT Images of Any Length over Non-Binary Alphabets. In 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 369, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{fici_et_al:LIPIcs.CPM.2026.13,
  author =	{Fici, Gabriele and Gabory, Est\'{e}ban and Romana, Giuseppe and Sciortino, Marinella},
  title =	{{Totally Unclustered BWT Images of Any Length over Non-Binary Alphabets}},
  booktitle =	{37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)},
  pages =	{13:1--13:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-420-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{369},
  editor =	{Bille, Philip and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2026.13},
  URN =		{urn:nbn:de:0030-drops-259399},
  doi =		{10.4230/LIPIcs.CPM.2026.13},
  annote =	{Keywords: Burrows-Wheeler Transform, BWT-runs, Repetitiveness Measure, Clustering Effect, Generalized de Bruijn Words}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2026.18
On Fréchet Traveling Salesmen Problems

Authors: Omrit Filtser, Tzalik Maimon, and Michal Moiseev

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract
The Fréchet distance is a well-studied distance measure between two curves. In this work, we demonstrate that the merit of Fréchet distance extends beyond evaluating similarity, and introduce a new setting in which it proves useful. Consider a situation where two agents are required to visit a given set of sites, while staying close to each other throughout their traversal. In this paper, we study problems where the goal is to construct two curves whose vertices are from a given set of points, under the constraint that the Fréchet distance between the curves is kept as small as possible. This problem can be viewed as a variant of the Traveling Salesman Problem (TSP), and thus may be of interest in routing, network planning and more. We present a near-linear algorithm for this problem under the discrete Fréchet distance, and explore several variants of the problem, including minimizing the lengths of the curves and balancing the number of sites assigned to each agent. Lastly, we prove that the problem is NP-hard under the continuous Fréchet Distance.
Cite as

Omrit Filtser, Tzalik Maimon, and Michal Moiseev. On Fréchet Traveling Salesmen Problems. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 18:1-18:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{filtser_et_al:LIPIcs.SWAT.2026.18,
  author =	{Filtser, Omrit and Maimon, Tzalik and Moiseev, Michal},
  title =	{{On Fr\'{e}chet Traveling Salesmen Problems}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{18:1--18:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.18},
  URN =		{urn:nbn:de:0030-drops-260545},
  doi =		{10.4230/LIPIcs.SWAT.2026.18},
  annote =	{Keywords: Fr\'{e}chet distance, traveling salesman problem}
}
Document
DOI: 10.4230/LIPIcs.FORC.2026.12
Tradeoffs in Privacy, Welfare, and Fairness for Facility Location

Authors: Sara Fish, Yannai A. Gonczarowski, Jason Z. Tang, and Salil Vadhan

Published in: LIPIcs, Volume 368, 7th Symposium on Foundations of Responsible Computing (FORC 2026)

Abstract
The differentially private (DP) facility location problem seeks to determine a socially optimal placement for a public facility while ensuring that each participating agent’s location remains private. In order to privatize its input data, a DP mechanism must inject noise into its output distribution, producing a placement that will have lower expected social welfare than the optimal spot for the facility. The privacy-induced welfare loss can be viewed as the "cost of privacy," illustrating a tradeoff between social welfare and privacy that has been the focus of prior work. Yet, the imposition of privacy also induces a third consideration that has not been similarly studied: fairness in how the "cost of privacy" is distributed across individuals. For instance, a mechanism may satisfy differential privacy with minimal social welfare loss, yet still be undesirable if that loss falls entirely on one individual. In this paper, we quantify this new notion of unfairness and design mechanisms for facility location that attempt to simultaneously optimize across these three objectives of privacy, social welfare, and fairness. Under this setup, we first derive an impossibility result, showing that privacy and fairness cannot be simultaneously guaranteed over all possible datasets that could represent the locations of individuals in a population. We then consider a relaxation of the original problem that still requires worst-case differential privacy, but only seeks fairness and appealing social welfare over smaller, more "realistic-looking" families of datasets. For this relaxation, we construct a DP mechanism and demonstrate that it is simultaneously optimal (or, for a harder family of datasets, near-optimal up to small factors) on fairness and social welfare. This suggests that while there is a tradeoff between privacy and each of social welfare and fairness, there is no additional tradeoff when we consider all three objectives simultaneously, provided that the population data is sufficiently natural.
Cite as

Sara Fish, Yannai A. Gonczarowski, Jason Z. Tang, and Salil Vadhan. Tradeoffs in Privacy, Welfare, and Fairness for Facility Location. In 7th Symposium on Foundations of Responsible Computing (FORC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 368, pp. 12:1-12:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{fish_et_al:LIPIcs.FORC.2026.12,
  author =	{Fish, Sara and Gonczarowski, Yannai A. and Tang, Jason Z. and Vadhan, Salil},
  title =	{{Tradeoffs in Privacy, Welfare, and Fairness for Facility Location}},
  booktitle =	{7th Symposium on Foundations of Responsible Computing (FORC 2026)},
  pages =	{12:1--12:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-419-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{368},
  editor =	{Lin, Huijia (Rachel)},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2026.12},
  URN =		{urn:nbn:de:0030-drops-259858},
  doi =		{10.4230/LIPIcs.FORC.2026.12},
  annote =	{Keywords: differential privacy, facility location, fairness, mechanism design}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.36
Upward Book Embeddings of Partitioned Digraphs

Authors: Giordano Da Lozzo, Fabrizio Frati, and Ignaz Rutter

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
In 1999, Heath, Pemmaraju, and Trenk [SIAM J. Comput. 28(4), 1999] extended the classic notion of book embeddings to digraphs, introducing the concept of upward book embeddings, in which the vertices must appear along the spine in a topological order and the edges are partitioned into pages, so that no two edges in the same page cross. For a partitioned digraph G = (V, ⋃^k_{i=1} E_i), that is, a digraph whose edge set is partitioned into k subsets, an upward book embedding is required to assign edges to pages as prescribed by the given partition. In a companion paper, Heath and Pemmaraju [SIAM J. Comput. 28(5), 1999] proved that the problem of testing the existence of an upward book embedding of a partitioned digraph is linear-time solvable for k = 1 and recently Akitaya, Demaine, Hesterberg, and Liu [GD, 2017] have shown the problem NP-complete for k ≥ 3. In this paper, we study upward book embeddings of partitioned digraphs and focus on the unsolved case k = 2. Our first main result is a novel characterization of the upward embeddings that support an upward book embedding in two pages. We exploit this characterization in several ways, and obtain a rich picture of the complexity landscape of the problem. First, we show that the problem remains NP-complete when k = 2, thus closing the complexity gap for the problem. Second, we show that, for an n-vertex partitioned digraph with a prescribed planar embedding, the existence of an upward book embedding that respects the given planar embedding can be tested in O(n log³ n) time. Finally, leveraging the SPQ(R)-tree decomposition of biconnected graphs into triconnected components, we present a cubic-time testing algorithm for biconnected directed partial 2-trees.
Cite as

Giordano Da Lozzo, Fabrizio Frati, and Ignaz Rutter. Upward Book Embeddings of Partitioned Digraphs. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 36:1-36:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dalozzo_et_al:LIPIcs.SoCG.2026.36,
  author =	{Da Lozzo, Giordano and Frati, Fabrizio and Rutter, Ignaz},
  title =	{{Upward Book Embeddings of Partitioned Digraphs}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{36:1--36:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.36},
  URN =		{urn:nbn:de:0030-drops-258424},
  doi =		{10.4230/LIPIcs.SoCG.2026.36},
  annote =	{Keywords: upward book embeddings, partitioned digraphs, SPQ-trees, 2-trees}
}
Document
DOI: 10.4230/OASIcs.NINeS.2026.10
Scalable Routing in a City-Scale Wi-Fi Network for Disaster Recovery

Authors: Ziqian Liu, Om Chabra, James Lynch, Aaron Martin, Chenning Li, and Hari Balakrishnan

Published in: OASIcs, Volume 139, 1st New Ideas in Networked Systems (NINeS 2026)

Abstract
This paper presents CityMesh, a city-scale decentralized mesh network designed for disaster recovery and emergency scenarios. When wide-area Internet connectivity is unavailable or severely degraded, CityMesh leverages both static access points and mobile devices equipped with Wi-Fi to provide intra-city connectivity and reach opportunistic gateways to the Internet (e.g., via satellite links). The main contribution of this paper is a scalable routing protocol that supports millions of devices, addressing a long-standing limitation of wireless mesh and mobile ad hoc networks. Unlike prior approaches, CityMesh exploits rich building-location and building-geometry data from widely available city maps to guide route computation, improving packet delivery while significantly reducing transmission overhead. Simulation results from 70 cities show that CityMesh improves packet delivery rates by 88% over WEAVE (a state-of-the-art geographic routing protocol). A campus-scale deployment of 300 Wi-Fi devices across 31 buildings shows the practical deployability of CityMesh. These results demonstrate the promise of map-aware routing as a foundation for scalable, resilient city-wide Wi-Fi networks.
Cite as

Ziqian Liu, Om Chabra, James Lynch, Aaron Martin, Chenning Li, and Hari Balakrishnan. Scalable Routing in a City-Scale Wi-Fi Network for Disaster Recovery. In 1st New Ideas in Networked Systems (NINeS 2026). Open Access Series in Informatics (OASIcs), Volume 139, pp. 10:1-10:31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{liu_et_al:OASIcs.NINeS.2026.10,
  author =	{Liu, Ziqian and Chabra, Om and Lynch, James and Martin, Aaron and Li, Chenning and Balakrishnan, Hari},
  title =	{{Scalable Routing in a City-Scale Wi-Fi Network for Disaster Recovery}},
  booktitle =	{1st New Ideas in Networked Systems (NINeS 2026)},
  pages =	{10:1--10:31},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-414-7},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{139},
  editor =	{Argyraki, Katerina and Panda, Aurojit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.NINeS.2026.10},
  URN =		{urn:nbn:de:0030-drops-255954},
  doi =		{10.4230/OASIcs.NINeS.2026.10},
  annote =	{Keywords: mesh networking, disaster recovery, geographic routing, scalability, Wi-Fi}
}
Document
DOI: 10.4230/OASIcs.NINeS.2026.18
TURBO: Utility-Aware Bandwidth Allocation for Cloud-Augmented Autonomous Control

Authors: Peter Schafhalter, Alexander Krentsel, Hongbo Wei, Joseph E. Gonzalez, Sylvia Ratnasamy, Scott Shenker, and Ion Stoica

Published in: OASIcs, Volume 139, 1st New Ideas in Networked Systems (NINeS 2026)

Abstract
Autonomous driving system progress has been driven by improvements in machine learning (ML) models, whose computational demands now exceed what edge devices alone can provide. The cloud offers abundant compute, but the network has long been treated as an unreliable bottleneck rather than a co-equal part of the autonomous vehicle control loop. We argue that this separation is no longer tenable: safety-critical autonomy requires co-design of control, models, and network resource allocation itself. We introduce TURBO, a cloud-augmented control framework that addresses this challenge, formulating bandwidth allocation and control pipeline configuration across both the car and cloud as a joint optimization problem. TURBO maximizes benefit to the car while guaranteeing safety in the face of highly variable network conditions. We implement TURBO and evaluate it in both simulation and real-world deployment, showing it can improve average accuracy by up to 15.6%pt over existing on-vehicle-only pipelines. Our code is made available at www.github.com/NetSys/turbo.
Cite as

Peter Schafhalter, Alexander Krentsel, Hongbo Wei, Joseph E. Gonzalez, Sylvia Ratnasamy, Scott Shenker, and Ion Stoica. TURBO: Utility-Aware Bandwidth Allocation for Cloud-Augmented Autonomous Control. In 1st New Ideas in Networked Systems (NINeS 2026). Open Access Series in Informatics (OASIcs), Volume 139, pp. 18:1-18:34, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{schafhalter_et_al:OASIcs.NINeS.2026.18,
  author =	{Schafhalter, Peter and Krentsel, Alexander and Wei, Hongbo and Gonzalez, Joseph E. and Ratnasamy, Sylvia and Shenker, Scott and Stoica, Ion},
  title =	{{TURBO: Utility-Aware Bandwidth Allocation for Cloud-Augmented Autonomous Control}},
  booktitle =	{1st New Ideas in Networked Systems (NINeS 2026)},
  pages =	{18:1--18:34},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-414-7},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{139},
  editor =	{Argyraki, Katerina and Panda, Aurojit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.NINeS.2026.18},
  URN =		{urn:nbn:de:0030-drops-256039},
  doi =		{10.4230/OASIcs.NINeS.2026.18},
  annote =	{Keywords: autonomous vehicles, bandwidth allocation, cloud computing, edge computing, machine learning}
}
Document
DOI: 10.4230/OASIcs.NINeS.2026.19
Simulate Before Sending: Rethinking Transport in Datacenter Networks

Authors: Dan Straussman, Isaac Keslassy, Alexander Shpiner, and Liran Liss

Published in: OASIcs, Volume 139, 1st New Ideas in Networked Systems (NINeS 2026)

Abstract
Existing transport protocols in commodity datacenter networks struggle to provide low collective completion times (CCTs) to AI training collectives, as packet losses and retransmissions significantly degrade performance. We propose dcSim, an efficient transport that achieves low CCTs and practically lossless performance with commodity switches. In dcSim, each packet first employs a small simulation probe to traverse the network and explore congestion along a candidate path. Only packets whose simulation probes succeed are then transmitted, expecting to succeed as well. Evaluations confirm that dcSim achieves faster CCTs than existing schemes, with small queues and virtually zero packet loss. Finally, dcSim also excels in adverse conditions, including oversubscribed topologies.
Cite as

Dan Straussman, Isaac Keslassy, Alexander Shpiner, and Liran Liss. Simulate Before Sending: Rethinking Transport in Datacenter Networks. In 1st New Ideas in Networked Systems (NINeS 2026). Open Access Series in Informatics (OASIcs), Volume 139, pp. 19:1-19:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{straussman_et_al:OASIcs.NINeS.2026.19,
  author =	{Straussman, Dan and Keslassy, Isaac and Shpiner, Alexander and Liss, Liran},
  title =	{{Simulate Before Sending: Rethinking Transport in Datacenter Networks}},
  booktitle =	{1st New Ideas in Networked Systems (NINeS 2026)},
  pages =	{19:1--19:22},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-414-7},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{139},
  editor =	{Argyraki, Katerina and Panda, Aurojit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.NINeS.2026.19},
  URN =		{urn:nbn:de:0030-drops-256044},
  doi =		{10.4230/OASIcs.NINeS.2026.19},
  annote =	{Keywords: Datacenter networks, transport protocols, AI training, lossless networks}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.69
Approximating q → p Norms of Non-Negative Matrices in Nearly-Linear Time

Authors: Etienne Objois and Adrian Vladu

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
We provide the first nearly-linear time algorithm for approximating 𝓁_{q → p}-norms of non-negative matrices, for q ≥ p ≥ 1. Our algorithm returns a (1-ε)-approximation to the matrix norm in time Õ(1/(q ε) ⋅ nnz(A)), where A is the input matrix, and improves upon the previous state of the art, which either proved convergence only in the limit [Boyd '74], or had very high polynomial running times [Bhaskara-Vijayraghavan, SODA '11]. Our algorithm is extremely simple, and is largely inspired from the coordinate-scaling approach used for positive linear program solvers. Our algorithm can readily be used in the [Englert-Räcke, FOCS '09] to improve the running time of constructing O(log n)-competitive 𝓁_p-oblivious routings.
Cite as

Etienne Objois and Adrian Vladu. Approximating q → p Norms of Non-Negative Matrices in Nearly-Linear Time. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 69:1-69:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{objois_et_al:LIPIcs.STACS.2026.69,
  author =	{Objois, Etienne and Vladu, Adrian},
  title =	{{Approximating q → p Norms of Non-Negative Matrices in Nearly-Linear Time}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{69:1--69:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.69},
  URN =		{urn:nbn:de:0030-drops-255585},
  doi =		{10.4230/LIPIcs.STACS.2026.69},
  annote =	{Keywords: matrix norm, Perron-Frobenius theory, oblivious routings, input-sparsity time, lp norm}
}
Document
DOI: 10.4230/LITES.10.2.1
Integrating Multi-Level Mixed-Criticality into MCTS for Robust Resource Management

Authors: Franco Cordeiro, Samuel Tardieu, and Laurent Pautet

Published in: LITES, Volume 10, Issue 2 (2025): Special Issue on Industrial Real-Time Systems. Leibniz Transactions on Embedded Systems, Volume 10, Issue 2

Abstract
Managing actions with uncertain resource costs is a complex challenge, particularly in autonomous robot mission planning. Robots are often assigned multiple objectives with varying criticality levels, ranging from catastrophic to minor impacts, where failures can significantly affect system safety. Uncertainties in worst-case costs of resources, such as energy and operating time - the time it takes to carry out an action - further complicate mission planning and execution. Monte Carlo Tree Search (MCTS) is a powerful tool for online planning, yet it struggles to account for uncertainty in worst-case cost estimations. Optimistic estimates risk resource shortages, while pessimistic ones lead to inefficient allocation. The Mixed-Criticality (MC) approach, originally developed for real-time systems to schedule critical tasks by allocating processing resources under Worst-Case Execution Time (WCET) uncertainty, provides a framework of rules, models and design principles. We claim this framework can be adapted to autonomous robot mission planning, where critical objectives are met through analogous allocation of different kinds of resources such as energy and operating time despite uncertainties. We propose enhancing MCTS with MC principles to handle uncertainty in worst-case costs across multiple resources and criticality of objectives. High-critical objectives must always be completed, regardless of resource constraints, while low-critical objectives operate flexibly, consuming resources within optimistic estimates when possible or being discarded when resources become scarce. This ensures efficient resource reallocation and prioritization of high-critical objectives. To implement this, we present (MC)²TS, a novel variant of MCTS that integrates MC principles for dynamic resource management. It supports more than two criticality levels to ensure that the most critical components meet the most stringent safety and reliability requirements, while also enabling robust resource management. By enabling replanning and mode changes, (MC)²TS improves MCTS’s efficiency and enhances MC systems’ adaptability to both degrading and improving resource conditions. We evaluate (MC)²TS in an active perception scenario, where a drone retrieves data from distributed sensors under unpredictable environmental conditions. (MC)²TS outperforms MCTS by achieving more objectives, adapting plans when costs drop. It explores more objective sequences, minimizes oversizing, and enhances efficiency. Balancing safety and performance, it monitors robot battery, mission and objective resource constraints such as deadlines. Its robustness ensures low-critical objectives do not compromise high-critical objectives, making it a reliable solution for complex systems characterized by uncertain resource costs and critical objectives.
Cite as

Franco Cordeiro, Samuel Tardieu, and Laurent Pautet. Integrating Multi-Level Mixed-Criticality into MCTS for Robust Resource Management. In LITES, Volume 10, Issue 2 (2025): Special Issue on Industrial Real-Time Systems. Leibniz Transactions on Embedded Systems, Volume 10, Issue 2, pp. 1:1-1:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@Article{cordeiro_et_al:LITES.10.2.1,
  author =	{Cordeiro, Franco and Tardieu, Samuel and Pautet, Laurent},
  title =	{{Integrating Multi-Level Mixed-Criticality into MCTS for Robust Resource Management}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{1:1--1:23},
  ISSN =	{2199-2002},
  year =	{2025},
  volume =	{10},
  number =	{2},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES.10.2.1},
  URN =		{urn:nbn:de:0030-drops-252339},
  doi =		{10.4230/LITES.10.2.1},
  annote =	{Keywords: Embedded Systems, Safety / Mixed-Critical Systems, Real-Time Systems, Energy Aware Systems}
}
Document
Poster Abstract
DOI: 10.4230/LIPIcs.GD.2025.49
Defective Linear Layouts of Graphs (Poster Abstract)

Authors: Michael A. Bekos, Carla Binucci, Emilio Di Giacomo, Walter Didimo, Luca Grilli, Maria Eleni Pavlidi, Alessandra Tappini, and Alexandra Weinberger

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract
A linear layout of a graph defines a total order of the vertices and partitions the edges into either stacks or queues, i.e., crossing-free and non-nested sets of edges along the order, respectively. In this work, we study defective linear layouts that allow forbidden patterns among edges of the same set. Our focus is on k-defective stack layouts and k-defective queue layouts, in which the conflict graph representing the forbidden patterns among the edges of each stack or queue has maximum degree at most k.
Cite as

Michael A. Bekos, Carla Binucci, Emilio Di Giacomo, Walter Didimo, Luca Grilli, Maria Eleni Pavlidi, Alessandra Tappini, and Alexandra Weinberger. Defective Linear Layouts of Graphs (Poster Abstract). In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 49:1-49:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bekos_et_al:LIPIcs.GD.2025.49,
  author =	{Bekos, Michael A. and Binucci, Carla and Di Giacomo, Emilio and Didimo, Walter and Grilli, Luca and Pavlidi, Maria Eleni and Tappini, Alessandra and Weinberger, Alexandra},
  title =	{{Defective Linear Layouts of Graphs}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{49:1--49:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.49},
  URN =		{urn:nbn:de:0030-drops-250350},
  doi =		{10.4230/LIPIcs.GD.2025.49},
  annote =	{Keywords: Linear layouts, stack layouts, queue layouts, defective layouts}
}
Document
DOI: 10.4230/LIPIcs.GD.2025.9
The Page Number of Monotone Directed Acyclic Outerplanar Graphs Is Four or Five

Authors: Jawaherul Md. Alam, Michael A. Bekos, Martin Gronemann, and Michael Kaufmann

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract
A k-page book embedding of a directed acyclic graph consists of a topological order of its vertices and a k-coloring of its edges, such that no two edges of the same color cross, that is, their endpoints do not alternate in the order. The minimum value of k for which such an embedding exists is referred to as the page number of the graph. In contrast to general directed acyclic planar graphs, which may have unbounded page number [SIAM J. Comput. 28(5), 1999], it was recently shown that directed acyclic outerplanar graphs have bounded page number. In particular, Jungeblut, Merker and Ueckerdt provided an upper bound of 24,776 on their page number [FOCS 2023: 1937-1952]. In this work, we focus on so-called monotone directed acyclic outerplanar graphs. Starting from a single edge, these graphs are constructed by iteratively connecting a new vertex to the endpoints of an existing edge on the outer face using either two incoming or two outgoing edges incident to it. These graphs have twist-number 4 [GD 2023: 135-151] (i.e., they admit a topological order in which no more than four edges pairwise cross), a property, which was leveraged by Jungeblut, Merker and Ueckerdt to show that their page number is at most 128. We lower this upper bound to 5 and we also provide a lower bound of 4. A notable consequence of our result is a significant improvement of the upper bound on the page number of general directed outerplanar graphs from 24,776 to 1,160.
Cite as

Jawaherul Md. Alam, Michael A. Bekos, Martin Gronemann, and Michael Kaufmann. The Page Number of Monotone Directed Acyclic Outerplanar Graphs Is Four or Five. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{alam_et_al:LIPIcs.GD.2025.9,
  author =	{Alam, Jawaherul Md. and Bekos, Michael A. and Gronemann, Martin and Kaufmann, Michael},
  title =	{{The Page Number of Monotone Directed Acyclic Outerplanar Graphs Is Four or Five}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{9:1--9:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.9},
  URN =		{urn:nbn:de:0030-drops-249952},
  doi =		{10.4230/LIPIcs.GD.2025.9},
  annote =	{Keywords: Book embeddings, page number, directed outerplanar graphs}
}
Document
DOI: 10.4230/LIPIcs.GD.2025.38
Stress in Graph Drawings: Perception, Preference, and Performance

Authors: Gavin J. Mooney, Jacob Miller, Michael Wybrow, Stephen Kobourov, and Helen C. Purchase

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract
Stress in a graph drawing has been a popular layout principle for more than two decades. Low stress drawings exhibit the property that the geometric distances between all pairs of nodes correlate with the shortest paths between them. The assumption has always been that low stress drawings are "nicer" and better support human perception and comprehension than high stress drawings. In this paper, we put these assumptions to the test. We use a normalised scale-independent and rotation-independent metric for stress; this is necessary to ensure strict controls on our experimental stimuli. We report on three experiments, exploring human perception of stress, preference for stress, and the effect of stress on a graph performance task. We conclude that people can see stress in a graph drawing, that they prefer low stress drawings, and that their performance in a shortest path task improves as stress decreases - thus empirically confirming long-standing assumptions.
Cite as

Gavin J. Mooney, Jacob Miller, Michael Wybrow, Stephen Kobourov, and Helen C. Purchase. Stress in Graph Drawings: Perception, Preference, and Performance. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 38:1-38:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{mooney_et_al:LIPIcs.GD.2025.38,
  author =	{Mooney, Gavin J. and Miller, Jacob and Wybrow, Michael and Kobourov, Stephen and Purchase, Helen C.},
  title =	{{Stress in Graph Drawings: Perception, Preference, and Performance}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{38:1--38:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.38},
  URN =		{urn:nbn:de:0030-drops-250240},
  doi =		{10.4230/LIPIcs.GD.2025.38},
  annote =	{Keywords: Graph Drawing, Graph Drawing Metrics, Stress, Visual Perception, User Study}
}
Document
DOI: 10.4230/LIPIcs.GD.2025.32
Planar Stories of Graph Drawings: Algorithms and Experiments

Authors: Carla Binucci, Sabine Cornelsen, Walter Didimo, Seok-Hee Hong, Eleni Katsanou, Maurizio Patrignani, Antonios Symvonis, and Samuel Wolf

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract
We address the problem of computing a dynamic visualization of a geometric graph G as a sequence of frames. Each frame shows only a portion of the graph but their union covers G entirely. The two main requirements of our dynamic visualization are: (i) guaranteeing drawing stability, so to preserve the user’s mental map; (ii) keeping the visual complexity of each frame low. To satisfy the first requirement, we never change the position of the vertices. Regarding the second requirement, we avoid edge crossings in each frame. More precisely, in the first frame we visualize a suitable subset of non-crossing edges; in each subsequent frame, exactly one new edge enters the visualization and all the edges that cross with it are deleted. We call such a sequence of frames a planar story of G. Our goal is to find a planar story whose minimum number of edges contemporarily displayed is maximized (i.e., a planar story that maximizes the minimum frame size). Besides studying our model from a theoretical point of view, we also design and experimentally compare different algorithms, both exact techniques and heuristics. These algorithms provide an array of alternative trade-offs between efficiency and effectiveness, also depending on the structure of the input graph.
Cite as

Carla Binucci, Sabine Cornelsen, Walter Didimo, Seok-Hee Hong, Eleni Katsanou, Maurizio Patrignani, Antonios Symvonis, and Samuel Wolf. Planar Stories of Graph Drawings: Algorithms and Experiments. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 32:1-32:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{binucci_et_al:LIPIcs.GD.2025.32,
  author =	{Binucci, Carla and Cornelsen, Sabine and Didimo, Walter and Hong, Seok-Hee and Katsanou, Eleni and Patrignani, Maurizio and Symvonis, Antonios and Wolf, Samuel},
  title =	{{Planar Stories of Graph Drawings: Algorithms and Experiments}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{32:1--32:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.32},
  URN =		{urn:nbn:de:0030-drops-250182},
  doi =		{10.4230/LIPIcs.GD.2025.32},
  annote =	{Keywords: Graph Drawing, Dynamic Graphs, Graph Stories, Heuristics, ILP}
}
Document
DOI: 10.4230/LIPIcs.GD.2025.30
Universal Quality Metrics for Graph Drawings: Which Graphs Excite Us Most?

Authors: Gavin J. Mooney, Tim Hegemann, Alexander Wolff, Michael Wybrow, and Helen C. Purchase

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract
Graphs are drawn for various purposes, and drawings are meant to display various features of a graph (such as planarity, Hamiltonicity). Still, there is a long history in measuring the quality of a graph drawing. Most of the metrics that have been implemented and used in large studies assume that graphs are drawn straight-line. Most of the studies use randomly generated graphs or one of very few existing benchmark sets that consist of graphs with a specific technical background (e.g., telecommunication networks). In this paper, we extend ten commonly used metrics to node-link diagrams where edges can be curves or polygonal chains. We implement these measures and use them to evaluate a new collection of graph drawings that we have extracted from 27 proceedings of the Graph Drawing conference using an automated pipeline. We compare the "metrics landscape" of our new benchmark set, the GD-collection-v1, which seems to mostly contain manually drawn graphs, to the metric landscape of a benchmark set with randomly generated graphs and computer-generated straight-line drawings that has been used in a recent study [Mooney et al.; PacificVis 2024]. Comparing the GD-collection-v1 with the Mooney at al. dataset reveals a distinct metrics landscape: GD drawings come from much smaller graphs (median vertex number 11 vs. 48) and therefore attain higher medians on most readability metrics. For example, Neighbourhood Preservation (0.5 vs. 0.239) is markedly higher in the GD-collection-v1. We also find that a large proportion of extracted drawings contain curved and/or polygonal edges (57%), motivating the extended metric definitions.
Cite as

Gavin J. Mooney, Tim Hegemann, Alexander Wolff, Michael Wybrow, and Helen C. Purchase. Universal Quality Metrics for Graph Drawings: Which Graphs Excite Us Most?. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 30:1-30:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{mooney_et_al:LIPIcs.GD.2025.30,
  author =	{Mooney, Gavin J. and Hegemann, Tim and Wolff, Alexander and Wybrow, Michael and Purchase, Helen C.},
  title =	{{Universal Quality Metrics for Graph Drawings: Which Graphs Excite Us Most?}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{30:1--30:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.30},
  URN =		{urn:nbn:de:0030-drops-250162},
  doi =		{10.4230/LIPIcs.GD.2025.30},
  annote =	{Keywords: Graph drawing metrics, metric landscape, straight-line drawings, polyline drawings, curved drawings, automated extraction of graph drawings}
}
Document
PhD Panel
DOI: 10.4230/OASIcs.DX.2025.16
Unsupervised Multimodal Learning for Fault Diagnosis and Prognosis - Application to Radiotherapy Systems (PhD Panel)

Authors: Kélian Poujade, Louise Travé-Massuyès, Jérémy Pirard, and Laure Vieillevigne

Published in: OASIcs, Volume 136, 36th International Conference on Principles of Diagnosis and Resilient Systems (DX 2025)

Abstract
Modern complex systems, such as radiotherapy machines, require robust strategies for fault detection, diagnosis, and prognosis to ensure operational continuity and patient safety. While data-driven methods have gained traction, few studies address diagnostic and prognostic tasks using multimodal operational data under unsupervised or semi-supervised learning settings. This gap is particularly critical given the scarcity of labeled failure data in real-world environments. This work aims to design a unified approach for fault detection, diagnosis, and prognosis using multimodal data in the absence of complete labeling. To this end, autoencoders (AEs) are employed due to their suitability for unsupervised and self-supervised learning, flexibility in handling heterogeneous data, and ability to construct latent representations optimized for various downstream tasks. A specific implementation based on a Long Short-Term Memory β-Variational Autoencoder (LSTM-β-VAE) was developed to detect anomalies in machine logs. This framework is applied to TomoTherapy® systems - a highly complex and under-explored use case within the radiotherapy domain. Initial results demonstrate strong anomaly detection performance on both a public benchmark dataset (HDFS) and a proprietary dataset derived from real-world TomoTherapy® machine faults. Beyond methodology, the paper includes a concise literature review of multimodal learning and data-driven diagnosis and prognosis with a focus on AEs. Based on this review, key research directions are identified for the continuation of the thesis, especially the integration of explainable AI as a means to enhance diagnosis capabilities in the absence of labeled faults.
Cite as

Kélian Poujade, Louise Travé-Massuyès, Jérémy Pirard, and Laure Vieillevigne. Unsupervised Multimodal Learning for Fault Diagnosis and Prognosis - Application to Radiotherapy Systems (PhD Panel). In 36th International Conference on Principles of Diagnosis and Resilient Systems (DX 2025). Open Access Series in Informatics (OASIcs), Volume 136, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{poujade_et_al:OASIcs.DX.2025.16,
  author =	{Poujade, K\'{e}lian and Trav\'{e}-Massuy\`{e}s, Louise and Pirard, J\'{e}r\'{e}my and Vieillevigne, Laure},
  title =	{{Unsupervised Multimodal Learning for Fault Diagnosis and Prognosis - Application to Radiotherapy Systems}},
  booktitle =	{36th International Conference on Principles of Diagnosis and Resilient Systems (DX 2025)},
  pages =	{16:1--16:17},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-394-2},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{136},
  editor =	{Quinones-Grueiro, Marcos and Biswas, Gautam and Pill, Ingo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.DX.2025.16},
  URN =		{urn:nbn:de:0030-drops-248058},
  doi =		{10.4230/OASIcs.DX.2025.16},
  annote =	{Keywords: Artificial Intelligence, Diagnosis, Prognosis, Radiotherapy machines}
}
  • Refine by Type
  • 52 Document/PDF
  • 45 Document/HTML

  • Refine by Publication Year
  • 8 2026
  • 34 2025
  • 1 2024
  • 2 2023
  • 3 2022
  • Show More...

  • Refine by Author
  • 2 Anselmo, Marcella
  • 2 Bekos, Michael A.
  • 2 Binucci, Carla
  • 2 Bonifati, Angela
  • 2 Castiglione, Giuseppa
  • Show More...

  • Refine by Series/Journal
  • 34 LIPIcs
  • 10 OASIcs
  • 5 LITES
  • 3 TGDK

  • Refine by Classification
  • 7 Theory of computation → Design and analysis of algorithms
  • 4 Mathematics of computing → Graph algorithms
  • 4 Mathematics of computing → Graph theory
  • 4 Theory of computation → Computational geometry
  • 3 Computer systems organization → Real-time systems
  • Show More...

  • Refine by Keyword
  • 3 Burrows-Wheeler Transform
  • 2 Algorithms
  • 2 Approximation algorithm
  • 2 Diagnosis
  • 2 GeoAI
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact