Laboratoire d’Informatique et Systèmes

On rigid regular graphs and a problem of Babai and Pultr

A graph is rigid if it only admits the identity endomorphism. We determine the minimum number of vertices of a rigid 𝑑 -regular graph for every 𝑑 . This extends results of Baron and Imrich (1969). Two rigid graphs are further mutually rigid if there is no homomorphism from one to...

Online Learning-Based Adaptive Hybrid Benders Decomposition for Risk-Averse Optimal Sizing

Optimal sizing problem (OSP) under uncertainty is often formulated as two-stage stochastic programming (2SP). However, this formulation typically introduces significant computational and RAM (memory) bottlenecks as the scenario size grows. Benders Decomposition (BD) is a popular...

Sampled-Based Guided Quantum Walk: Non-variational quantum algorithm for combinatorial optimization

We introduce SamBa-GQW, a novel quantum algorithm for solving binary combinatorial optimization problems of arbitrary degree with no use of any classical optimizer. The algorithm is based on a continuous-time quantum walk on the solution space represented as a graph. The walker e...

Tight (Double) Exponential Bounds for Identification Problems: Locating-Dominating Set and Test Cover

Abstract. We investigate fine-grained algorithmic aspects for classical identification problems in graphs, namely, Locating-Dominating Set, and in set systems, namely, Test Cover. In the first problem, an input is a graph [Formula: see text] on [Formula: see text] vertices and an...

Dynamic Trajectory Planning for Urban Traffic Using Deep Learning-Based Traffic Prediction

Abstract Traditional trajectory planning systems in navigation applications generate routes based on the current traffi conditions at the time of departure. However, traffi dynamics are highly variable, and aroute that is initially optimal may become congested during the trip, le...

Regulation-aware combinatorial optimization of energy community formation under geographic proximity constraints

Renewable Energy Communities (RECs) enable collective self-consumption by allowing geographically proximate households to share locally generated renewable energy. While most existing studies optimize the operation of a pre-defined community, the prior problem of how to partition...