Buchumschlag

A logarithmic approximation of linearly ordered colourings

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Håstad, Johan, Martinsson, Björn, Nakajima, Tamio-Vesa, Živný, Stanislav
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Combinatorics Discrete Mathematics Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

An approximation algorithm for Maximum DiCut vs. Cut
von: Nakajima, Tamio-Vesa, et al.
Veröffentlicht: (2024)

Maximum $k$- vs. $\ell$-colourings of graphs
von: Nakajima, Tamio-Vesa, et al.
Veröffentlicht: (2023)

A Dichotomy for Maximum PCSPs on Graphs
von: Nakajima, Tamio-Vesa, et al.
Veröffentlicht: (2024)

Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa
von: Bedert, Benjamin, et al.
Veröffentlicht: (2025)

On the complexity of symmetric vs. functional PCSPs
von: Nakajima, Tamio-Vesa, et al.
Veröffentlicht: (2022)

Complexity of approximate conflict-free, linearly-ordered, and nonmonochromatic hypergraph colourings
von: Nakajima, Tamio-Vesa, et al.
Veröffentlicht: (2025)

1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise
von: Ciardo, Lorenzo, et al.
Veröffentlicht: (2023)

Additive Sparsification of CSPs
von: Pelleg, Eden, et al.
Veröffentlicht: (2021)

Maximum And- vs. Even-SAT
von: Nakajima, Tamio-Vesa, et al.
Veröffentlicht: (2024)

A Strongly Polynomial-Time Algorithm for Weighted General Factors with Three Feasible Degrees
von: Shao, Shuai, et al.
Veröffentlicht: (2023)

Semidefinite programming and linear equations vs. homomorphism problems
von: Ciardo, Lorenzo, et al.
Veröffentlicht: (2023)

The periodic structure of local consistency
von: Ciardo, Lorenzo, et al.
Veröffentlicht: (2024)

Deterministic approximation for the volume of the truncated fractional matching polytope
von: Guo, Heng, et al.
Veröffentlicht: (2024)

A linear-time algorithm for $(1+ε)Δ$-edge-coloring
von: Bernshteyn, Anton, et al.
Veröffentlicht: (2024)

Quasi-linear distance query reconstruction for graphs of bounded treelength
von: Bastide, Paul, et al.
Veröffentlicht: (2024)

Deterministic approximate counting of colorings with fewer than $2Δ$ colors via absence of zeros
von: Bencs, Ferenc, et al.
Veröffentlicht: (2024)

Almost-linear time parameterized algorithm for rankwidth via dynamic rankwidth
von: Korhonen, Tuukka, et al.
Veröffentlicht: (2024)

A characterization of testable hypergraph properties
von: Joos, Felix, et al.
Veröffentlicht: (2017)

A Uniformly Random Solution to Algorithmic Redistricting
von: Cai, Jin-Yi, et al.
Veröffentlicht: (2024)

A Faster Deterministic Algorithm for Mader's $\mathcal{S}$-Path Packing
von: Iwata, Satoru, et al.
Veröffentlicht: (2024)

A Polynomial-Time Approximation Algorithm for Complete Interval Minors
von: Bourneuf, Romain, et al.
Veröffentlicht: (2025)

A Structural Linear-Time Algorithm for Computing the Tutte Decomposition
von: Bourneuf, Romain, et al.
Veröffentlicht: (2025)

A Quadratic Vertex Kernel and a Subexponential Algorithm for Subset-FAST
von: Jana, Satyabrata, et al.
Veröffentlicht: (2025)

A Fast Algorithm for Finding Minimum Weight Cycles in Mining Cyclic Graph Topologies
von: Shakeri, Heman, et al.
Veröffentlicht: (2025)

A new width parameter of graphs based on edge cuts: $α$-edge-crossing width
von: Chang, Yeonsu, et al.
Veröffentlicht: (2023)

A Near-Linear-Time Algorithm for Finding a Well-Spread Perfect Matching in Bridgeless Cubic Graphs
von: Ghanbari, Babak, et al.
Veröffentlicht: (2026)

Approximating maximum-size properly colored forests
von: Bai, Yuhang, et al.
Veröffentlicht: (2024)

Problems on Group-labeled Matroid Bases
von: Hörsch, Florian, et al.
Veröffentlicht: (2024)

$α_i$-Metric Graphs: Hyperbolicity
von: Dragan, Feodor F., et al.
Veröffentlicht: (2024)

Rainbow Arborescence Conjecture
von: Bérczi, Kristóf, et al.
Veröffentlicht: (2024)

Exact and Heuristic Computation of the Scanwidth of Directed Acyclic Graphs
von: Holtgrefe, Niels, et al.
Veröffentlicht: (2024)

Cuts in Graphs with Matroid Constraints
von: Banik, Aritra, et al.
Veröffentlicht: (2024)

Robust Contraction Decomposition for Minor-Free Graphs and its Applications
von: Bandyapadhyay, Sayan, et al.
Veröffentlicht: (2024)

Randomized Greedy Online Edge Coloring Succeeds for Dense and Randomly-Ordered Graphs
von: Dudeja, Aditi, et al.
Veröffentlicht: (2024)

Clique-free t-matchings in degree-bounded graphs
von: Paluch, Katarzyna, et al.
Veröffentlicht: (2024)

On the sizes of BDDs and ZDDs representing matroids
von: Emoto, Hiromi, et al.
Veröffentlicht: (2024)

On the number of $k$-mers admitting a given lexicographical minimizer
von: Ingels, Florian, et al.
Veröffentlicht: (2024)

Generalising the maximum independent set algorithm via Boolean networks
von: Gadouleau, Maximilien, et al.
Veröffentlicht: (2024)

Sparsest cut and eigenvalue multiplicities on low degree Abelian Cayley graphs
von: d'Orsi, Tommaso, et al.
Veröffentlicht: (2024)

On the enumeration of signatures of XOR-CNF's
von: Creignou, Nadia, et al.
Veröffentlicht: (2024)