Buchumschlag

The complexity of computing the period and the exponent of a digraph

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Kiefer, Stefan, Ryzhikov, Andrew
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Discrete Mathematics Combinatorics
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Invertibility of digraphs and tournaments
von: Alon, Noga, et al.
Veröffentlicht: (2022)

An analogue of Reed's conjecture for digraphs
von: Kawarabayashi, Ken-ichi, et al.
Veröffentlicht: (2024)

Generalized DP-colorings of digraphs
von: Picasarri-Arrieta, Lucas, et al.
Veröffentlicht: (2025)

$(Δ-1)$-dicolouring of digraphs
von: Harutyunyan, Ararat, et al.
Veröffentlicht: (2025)

Algorithms and hardness for Metric Dimension on digraphs
von: Dailly, Antoine, et al.
Veröffentlicht: (2023)

Karp's patching algorithm on dense digraph
von: Frieze, Alan
Veröffentlicht: (2025)

Subdivisions in dicritical digraphs with large order or digirth
von: Picasarri-Arrieta, Lucas, et al.
Veröffentlicht: (2024)

Redicolouring digraphs: directed treewidth and cycle-degeneracy
von: Nisse, Nicolas, et al.
Veröffentlicht: (2023)

Orthogonality between acyclic subdigraphs and paths in digraphs
von: Silva, Caroline A. de Paula, et al.
Veröffentlicht: (2026)

Dividing sums of cycles in the semiring of functional digraphs
von: Bridoux, Florian, et al.
Veröffentlicht: (2025)

There is no prime functional digraph: Seifert's proof revisited
von: Richard, Adrien
Veröffentlicht: (2025)

Bounding the chromatic number of dense digraphs by arc neighborhoods
von: Klingelhoefer, Felix, et al.
Veröffentlicht: (2023)

Unavoidable butterfly minors in digraphs of large cycle rank
von: Hatzel, Meike, et al.
Veröffentlicht: (2025)

On the minimum number of inversions to make a digraph $k$-(arc-)strong
von: Duron, Julien, et al.
Veröffentlicht: (2023)

Extremal digraphs for open neighbourhood location-domination and identifying codes
von: Foucaud, Florent, et al.
Veröffentlicht: (2023)

(Claw, C_3)-free digraphs with unbounded dichromatic number
von: Aubian, Guillaume, et al.
Veröffentlicht: (2026)

Complexity results on the decomposition of a digraph into directed linear forests and out-stars
von: Hörsch, Florian, et al.
Veröffentlicht: (2024)

On shortest products for nonnegative matrix mortality
von: Ryzhikov, Andrew
Veröffentlicht: (2024)

Careful synchronisation and the diameter of transformation semigroups with few generators
von: Ryzhikov, Andrew
Veröffentlicht: (2025)

Minimum number of arcs in $k$-critical digraphs with order at most $2k-1$
von: Picasarri-Arrieta, Lucas, et al.
Veröffentlicht: (2023)

Critical exponent of binary words with few distinct palindromes
von: Dvořáková, L'ubomíra, et al.
Veröffentlicht: (2023)

Internally-disjoint directed pendant Steiner trees with three terminal vertices in Cartesian product digraphs
von: Yu, Shanshan, et al.
Veröffentlicht: (2026)

Cop numbers of periodic graphs
von: De Carufel, Jean-Lou, et al.
Veröffentlicht: (2023)

Graceful coloring is computationally hard
von: Antony, Cyriac, et al.
Veröffentlicht: (2024)

Revisiting classical results on kernels in digraphs
von: Langlois, Hélène, et al.
Veröffentlicht: (2025)

Neighborhood complexity of planar graphs
von: Joret, Gwenaël, et al.
Veröffentlicht: (2023)

Computational complexity of covering regular trees
von: Bok, Jan, et al.
Veröffentlicht: (2025)

Solving systems of equations on antichains for the computation of the ninth Dedekind Number
von: De Causmaecker, Patrick, et al.
Veröffentlicht: (2024)

Odd coloring graphs with linear neighborhood complexity
von: Davies, James, et al.
Veröffentlicht: (2025)

Profile and neighbourhood complexity of graphs excluding a minor and tree-structured graphs
von: Beaudou, Laurent, et al.
Veröffentlicht: (2025)

Bounding the Weisfeiler-Leman Dimension via a Depth Analysis of I/R-Trees
von: Kiefer, Sandra, et al.
Veröffentlicht: (2024)

Boundary rigidity of finite CAT(0) cube complexes
von: Chalopin, Jérémie, et al.
Veröffentlicht: (2023)

Feedback vertex sets of planar digraphs with fixed digirth
von: Dreyer, Simon, et al.
Veröffentlicht: (2026)

Note about the complexity of the acyclic orientation with parity constraint problem
von: Gravier, Sylvain, et al.
Veröffentlicht: (2025)

Powers of large matrices on GPU platforms to compute the Roman domination number of cylindrical graphs
von: Martínez, J. A., et al.
Veröffentlicht: (2024)

HPC acceleration of large (min, +) matrix products to compute domination-type parameters in graphs
von: Garzón, E. M., et al.
Veröffentlicht: (2024)

Partial vertex covers and the complexity of some problems concerning static and dynamic monopolies
von: Soltani, Hossein, et al.
Veröffentlicht: (2018)

Parameterized complexity of $r$-Hop, $r$-Step, and $r$-Hop Roman Domination
von: Das, Sandip, et al.
Veröffentlicht: (2026)

Strong isometric path complexity of graphs: Asymptotic minors, restricted holes, and graph operations
von: Chakraborty, Dibyayan, et al.
Veröffentlicht: (2025)

Enumerating Two-Orbit Graphs
von: Seka, David, et al.
Veröffentlicht: (2026)