Copertina

Distance to Transitivity: New Parameters for Taming Reachability in Temporal Graphs

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Casteigts, Arnaud, Morawietz, Nils, Wolf, Petra
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

On the Hardness of Finding Temporally Connected Subgraphs of Any Size
di: Casteigts, Arnaud, et al.
Pubblicazione: (2026)

Recognizing and Realizing Temporal Reachability Graphs
di: Erlebach, Thomas, et al.
Pubblicazione: (2025)

Timeline Problems in Temporal Graphs: Vertex Cover vs. Dominating Set
di: Herrmann, Anton, et al.
Pubblicazione: (2025)

Realization of Temporally Connected Graphs Based on Degree Sequences
di: Casteigts, Arnaud, et al.
Pubblicazione: (2025)

The Parameter Report: An Orientation Guide for Data-Driven Parameterization
di: Komusiewicz, Christian, et al.
Pubblicazione: (2025)

Scalable Neighborhood Local Search for Single-Machine Scheduling with Family Setup Times
di: Balzereit, Kaja, et al.
Pubblicazione: (2024)

Parameterized Local Search for Max $c$-Cut
di: Garvardt, Jaroslav, et al.
Pubblicazione: (2024)

In search of the lost tree: Hardness and relaxation of spanning trees in temporal graphs
di: Casteigts, Arnaud, et al.
Pubblicazione: (2023)

A Parameterized-Complexity Framework for Finding Local Optima
di: Ganian, Robert, et al.
Pubblicazione: (2026)

Fantastic Flips and Where to Find Them: A General Framework for Parameterized Local Search on Partitioning Problems
di: Grüttemeier, Niels, et al.
Pubblicazione: (2025)

Vector TSP: A Traveling Salesperson Problem with Racetrack-like Acceleration Constraints
di: Casteigts, Arnaud, et al.
Pubblicazione: (2020)

The Descriptive Complexity of Relation Modification Problems
di: Chudigiewitsch, Florian, et al.
Pubblicazione: (2026)

Complexity of Local Search for Euclidean Clustering Problems
di: Manthey, Bodo, et al.
Pubblicazione: (2023)

Maximum Reachability Orientation of Mixed Graphs
di: Hörsch, Florian
Pubblicazione: (2025)

Temporal Reachability Dominating Sets: contagion in temporal graphs
di: Kutner, David C., et al.
Pubblicazione: (2023)

The Complexity of Transitively Orienting Temporal Graphs
di: Mertzios, George B., et al.
Pubblicazione: (2021)

Reachability In Simple Neural Networks
di: Sälzer, Marco, et al.
Pubblicazione: (2022)

Reachability of Independent Sets and Vertex Covers Under Extended Reconfiguration Rules
di: Hirahara, Shuichi, et al.
Pubblicazione: (2025)

Domination in Diameter-Two Graphs and the 2-Club Cluster Vertex Deletion Parameter
di: Abu-Khzam, Faisal N., et al.
Pubblicazione: (2024)

Reachability of Fair Allocations via Sequential Exchanges
di: Igarashi, Ayumi, et al.
Pubblicazione: (2023)

New Quantum Algorithms for Computing Quantum Entropies and Distances
di: Wang, Qisheng, et al.
Pubblicazione: (2022)

Inner-approximate Reachability Computation via Zonotopic Boundary Analysis
di: Ren, Dejin, et al.
Pubblicazione: (2024)

Galois Energy Games: To Solve All Kinds of Quantitative Reachability Problems
di: Lemke, Caroline, et al.
Pubblicazione: (2025)

Temporal Cycle Detection and Acyclic Temporization
di: de Andrade, Davi, et al.
Pubblicazione: (2025)

Recursion and proof theoretical characterizations of small circuit classes with modulo counting via discrete differential equations (long version)
di: Antonelli, Melissa, et al.
Pubblicazione: (2026)

Dynamic Planar Graph Isomorphism is in DynFO
di: Datta, Samir, et al.
Pubblicazione: (2026)

Matching and Edge Cover in Temporal Graphs
di: Cioni, Lapo, et al.
Pubblicazione: (2025)

Constant-Cost Communication is not Reducible to k-Hamming Distance
di: Fang, Yuting, et al.
Pubblicazione: (2024)

From Graph Properties to Graph Parameters: Tight Bounds for Counting on Small Subgraphs
di: Döring, Simon, et al.
Pubblicazione: (2024)

Total Variation Distance for Product Distributions is $\#\mathsf{P}$-Complete
di: Bhattacharyya, Arnab, et al.
Pubblicazione: (2024)

PCP-free APX-Hardness of Nearest Codeword and Minimum Distance
di: Bhattiprolu, Vijay, et al.
Pubblicazione: (2025)

A Near-Optimal Polynomial Distance Lemma Over Boolean Slices
di: Amireddy, Prashanth, et al.
Pubblicazione: (2025)

Reachability in Geometrically $d$-Dimensional VASS
di: Fu, Yuxi, et al.
Pubblicazione: (2025)

Nonogram: Complexity of Inference and Phase Transition Behavior
di: Foote, Aaron, et al.
Pubblicazione: (2025)

Explaining the Ubiquity of Phase Transitions in Decision Problems
di: Jackson, Andrew
Pubblicazione: (2025)

Separations between Combinatorial Measures for Transitive Functions
di: Chakraborty, Sourav, et al.
Pubblicazione: (2021)

The Reachability Problem for Neural-Network Control Systems
di: Schilling, Christian, et al.
Pubblicazione: (2024)

The Complexity Classes of Hamming Distance Recoverable Robust Problems
di: Grüne, Christoph
Pubblicazione: (2022)

The Simultaneous Interval Number: A New Width Parameter that Measures the Similarity to Interval Graphs
di: Beisegel, Jesse, et al.
Pubblicazione: (2024)

Representing Matroids over the Reals is $\exists \mathbb R$-complete
di: Kim, Eun Jung, et al.
Pubblicazione: (2023)