Copertina

Asymptotic Lower Bounds for the Feedback Arc Set Problem in Random Graphs

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Diamond, Harvey, Kon, Mark, Raphael, Louise
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Combinatorics 05C80 (Primary) 05C85, 68W40 (Secondary)
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Asymptotics of the Minimal Feedback Arc Set in Erdős-Rényi Graphs
di: Diamond, Harvey, et al.
Pubblicazione: (2024)

On Conjectures concerning the Labeled Coupon Collector Problem
di: Barak-Pelleg, Dina, et al.
Pubblicazione: (2025)

A $5/4$-Approximation for Two-Edge Connectivity
di: Bosch-Calvo, Miguel, et al.
Pubblicazione: (2024)

Regular bipartite decompositions of pseudorandom graphs
di: Ferber, Asaf, et al.
Pubblicazione: (2024)

Zero-free regions of partition functions with applications to algorithms and graph limits
di: Regts, Guus
Pubblicazione: (2015)

Finding cliques and dense subgraphs using edge queries
di: Csóka, Endre, et al.
Pubblicazione: (2023)

Improved Approximation Algorithms for Path and Forest Augmentation via a Novel Relaxation
di: Hommelsheim, Felix
Pubblicazione: (2025)

A $4/3$ Approximation for $2$-Vertex-Connectivity
di: Bosch-Calvo, Miguel, et al.
Pubblicazione: (2023)

Lower Bounds for the Pfaffian Number of Graphs
di: Junchaya, Enrique, et al.
Pubblicazione: (2026)

Young domination on Hamming rectangles
di: Gravner, Janko, et al.
Pubblicazione: (2025)

Algorithmic releases on the spanning trees of suitable graphs
di: Imbesi, Maurizio, et al.
Pubblicazione: (2017)

Vector encoding of phylogenetic trees by ordered leaf attachment
di: Richman, Harry, et al.
Pubblicazione: (2025)

Minimal obstructions to $C_5$-coloring in hereditary graph classes
di: Goedgebeur, Jan, et al.
Pubblicazione: (2024)

Large deviations of the greedy independent set algorithm on sparse random graphs
di: Kolesnik, Brett
Pubblicazione: (2020)

Towards a dichotomy for the switch list homomorphism problem for signed graphs
di: Kim, Hyobin, et al.
Pubblicazione: (2021)

Improved lower bounds for the maximum order of an induced acyclic subgraph
di: Asgarli, Shamil, et al.
Pubblicazione: (2025)

Recolouring Homomorphisms to triangle-free reflexive graphs
di: Lee, Jae-baek, et al.
Pubblicazione: (2021)

Oriented Colouring Graphs of Bounded Degree and Degeneracy
di: Clow, Alexander, et al.
Pubblicazione: (2023)

Cup Stacking in Graphs
di: Fay, Paul, et al.
Pubblicazione: (2023)

The spread of fire on a random multigraph
di: Goldschmidt, Christina, et al.
Pubblicazione: (2017)

Limiting Behavior of Resistances in Triangular Graphs
di: Hendel, Russell Jay
Pubblicazione: (2021)

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

5-Coloring Planar Graphs with a Color Class of Order at Most $|V|/6$
di: Inoue, Yuta, et al.
Pubblicazione: (2025)

A new bound in Majority Dynamics on Random Graphs
di: Jaffe, Sean
Pubblicazione: (2025)

Cofinality of Regular Tournaments
di: Hatem, Omar, et al.
Pubblicazione: (2026)

Slavic Techniques for Hat Guessing Algorithms
di: McInnis, I. M. J.
Pubblicazione: (2025)

Diameter Thresholds of Random Cayley Graphs
di: Christofides, Demetres, et al.
Pubblicazione: (2026)

DP-Coloring of Graphs from Random Covers
di: Bernshteyn, Anton, et al.
Pubblicazione: (2023)

Tight complexity bounds for diagram commutativity verification
di: Malko, Artem, et al.
Pubblicazione: (2025)

The Antisymmetric Line Graph
di: Bal, Hartosh Singh
Pubblicazione: (2026)

A greedy heuristic for graph burning
di: García-Díaz, Jesús, et al.
Pubblicazione: (2024)

Asymptotic normality for general subtree counts in conditioned Galton--Watson trees
di: Rakotoniaina, Fameno, et al.
Pubblicazione: (2026)

A tame vs. feral dichotomy for graph classes excluding an induced minor or induced topological minor
di: Milanič, Martin, et al.
Pubblicazione: (2024)

A note on limits of sequences of binary trees
di: Grübel, Rudolf
Pubblicazione: (2023)

Coloring graphs as complete graph invariants
di: Asgarli, Shamil, et al.
Pubblicazione: (2025)

Tree independence number V. Walls and claws
di: Chudnovsky, Maria, et al.
Pubblicazione: (2025)

4-cop-win graphs have at least 19 vertices
di: Turcotte, Jérémie, et al.
Pubblicazione: (2020)

Analysis of Clustering and Degree Index in Random Graphs and Complex Networks
di: Işlak, Ümit, et al.
Pubblicazione: (2024)

On the joint embedding property for cographs and trees
di: Carter, Daniel
Pubblicazione: (2024)

An Analysis of Optimizer Choice on Energy Efficiency and Performance in Neural Network Training
di: Almog, Tom
Pubblicazione: (2025)