Cover Image

Karp's patching algorithm on dense digraph

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Frieze, Alan
Format:	Preprint
Published:	2025
Subjects:	Combinatorics Discrete Mathematics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Karp's patching algorithm on random perturbations of dense digraphs
by: Frieze, Alan, et al.
Published: (2022)

Rainbow copies of spanning subgraphs
by: Cooper, Colin, et al.
Published: (2025)

Binomial Random Matroids
by: Bennett, Patrick, et al.
Published: (2026)

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

Building Hamiltonian Cycles in the Semi-Random Graph Process in Less Than $2n$ Rounds
by: Frieze, Alan, et al.
Published: (2023)

Invertibility of digraphs and tournaments
by: Alon, Noga, et al.
Published: (2022)

Generalized DP-colorings of digraphs
by: Picasarri-Arrieta, Lucas, et al.
Published: (2025)

$(Δ-1)$-dicolouring of digraphs
by: Harutyunyan, Ararat, et al.
Published: (2025)

An analogue of Reed's conjecture for digraphs
by: Kawarabayashi, Ken-ichi, et al.
Published: (2024)

Algorithms and hardness for Metric Dimension on digraphs
by: Dailly, Antoine, et al.
Published: (2023)

Dividing sums of cycles in the semiring of functional digraphs
by: Bridoux, Florian, et al.
Published: (2025)

There is no prime functional digraph: Seifert's proof revisited
by: Richard, Adrien
Published: (2025)

Redicolouring digraphs: directed treewidth and cycle-degeneracy
by: Nisse, Nicolas, et al.
Published: (2023)

Orthogonality between acyclic subdigraphs and paths in digraphs
by: Silva, Caroline A. de Paula, et al.
Published: (2026)

The complexity of computing the period and the exponent of a digraph
by: Kiefer, Stefan, et al.
Published: (2024)

Subdivisions in dicritical digraphs with large order or digirth
by: Picasarri-Arrieta, Lucas, et al.
Published: (2024)

Unavoidable butterfly minors in digraphs of large cycle rank
by: Hatzel, Meike, et al.
Published: (2025)

Extremal digraphs for open neighbourhood location-domination and identifying codes
by: Foucaud, Florent, et al.
Published: (2023)

(Claw, C_3)-free digraphs with unbounded dichromatic number
by: Aubian, Guillaume, et al.
Published: (2026)

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

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

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

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

Efficient polynomial-time approximation scheme for the genus of dense graphs
by: Jing, Yifan, et al.
Published: (2020)

The Closed Geodetic Game: algorithms and strategies
by: Dailly, Antoine, et al.
Published: (2024)

Revisiting classical results on kernels in digraphs
by: Langlois, Hélène, et al.
Published: (2025)

Fast algorithm for $S$-packing coloring of Halin graphs
by: Zhang, Xin, et al.
Published: (2025)

Faster 3-colouring algorithm for graphs of diameter 3
by: Groenland, Carla, et al.
Published: (2026)

A verified implementation of the Misra and Gries edge coloring algorithm
by: Bhoja, Arohee
Published: (2025)

Complexity and algorithms for Arc-Kayles and Non-Disconnecting Arc-Kayles
by: Burke, Kyle, et al.
Published: (2024)

Feedback vertex sets of planar digraphs with fixed digirth
by: Dreyer, Simon, et al.
Published: (2026)

Las Vegas algorithms to generate universal cycles and de Bruijn sequences uniformly at random
by: Sawada, Joe, et al.
Published: (2025)

Oriented trees in $O(k \sqrt{k})$-chromatic digraphs, a subquadratic bound for Burr's conjecture
by: Bessy, Stéphane, et al.
Published: (2024)

On constrained intersection representations of graphs and digraphs
by: Cicalese, Ferdinando, et al.
Published: (2025)

Polynomial-delay generation of functional digraphs up to isomorphism
by: Defrain, Oscar, et al.
Published: (2023)

Crossing numbers of dense graphs on surfaces
by: Hubard, Alfredo, et al.
Published: (2025)

A characterization of interval nest digraphs
by: Alcantar, Ayelén, et al.
Published: (2026)

Asymptotic size of the Karp-Sipser Core in Configuration Model
by: Chatterjee, Arnab, et al.
Published: (2025)

Complexity and algorithms for matching cut problems in graphs without long induced paths and cycles
by: Le, Hoang-Oanh, et al.
Published: (2023)

Non-crossing $H$-graphs: a generalization of proper interval graphs admitting FPT algorithms
by: Bonomo-Braberman, Flavia, et al.
Published: (2025)