Cover Image

Greed is slow on sparse graphs of oriented valued constraints

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kaznatcheev, Artem, Alferez, Sofia Vazquez
Format:	Preprint
Published:	2025
Subjects:	Discrete Mathematics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

When is local search both effective and efficient?
by: Kaznatcheev, Artem, et al.
Published: (2024)

Binary constraints on one additional variable can create exponential ascents
by: Cohen, David A., et al.
Published: (2026)

All ascents exponential from valued constraint graphs of pathwidth three
by: Kaznatcheev, Artem, et al.
Published: (2026)

Local search for valued constraint satisfaction parameterized by treedepth
by: Kaznatcheev, Artem
Published: (2024)

Exponential Steepest Ascent from Valued Constraint Graphs of Pathwidth Four
by: Kaznatcheev, Artem, et al.
Published: (2024)

Minimum stationary values of sparse random directed graphs
by: Cai, Xing Shi, et al.
Published: (2020)

Equitable coloring of sparse graphs
by: Liu, Weichan, et al.
Published: (2024)

Canonical labelling of sparse random graphs
by: Verbitsky, Oleg, et al.
Published: (2024)

Twin-width of sparse random graphs
by: Hendrey, Kevin, et al.
Published: (2023)

Lower bounds for dominating set reconfiguration on sparse (directed) graphs
by: Dirks, Jona, et al.
Published: (2025)

Long induced paths in sparse graphs and graphs with forbidden patterns
by: Duron, Julien, et al.
Published: (2024)

On cuts of small chromatic number in sparse graphs
by: Aubian, Guillaume, et al.
Published: (2025)

On locating and neighbor-locating colorings of sparse graphs
by: Chakraborty, Dipayan, et al.
Published: (2023)

Monitoring arc-geodetic sets of oriented graphs
by: Das, Tapas, et al.
Published: (2024)

Sample compression schemes for balls in structurally sparse graphs
by: Bourneuf, Romain, et al.
Published: (2026)

On arc-density of pushably $3$-critical oriented graphs
by: Das, Tapas, et al.
Published: (2025)

On the inversion number of oriented graphs
by: Bang-Jensen, Jørgen, et al.
Published: (2021)

Note about the complexity of the acyclic orientation with parity constraint problem
by: Gravier, Sylvain, et al.
Published: (2025)

Some polynomial classes for the acyclic orientation with parity constraint problem
by: Gravier, Sylvain, et al.
Published: (2026)

Acyclic dichromatic number of oriented graphs
by: Bang-Jensen, Jørgen, et al.
Published: (2025)

On semi-transitive orientability of circulant graphs
by: Srinivasan, Eshwar, et al.
Published: (2024)

A quasi-optimal upper bound for induced paths in sparse graphs
by: Couëtoux, Basile, et al.
Published: (2025)

On the $(\leq p)$-inversion diameter of oriented graphs
by: Havet, Frédéric, et al.
Published: (2026)

Weakly-sparse and strongly flip-flat classes of graphs are uniformly almost-wide
by: Ghasemi, Fatemeh, et al.
Published: (2025)

Krenn-Gu conjecture for sparse graphs
by: Chandran, L. Sunil, et al.
Published: (2024)

On the minimum number of arcs in $4$-dicritical oriented graphs
by: Havet, Frédéric, et al.
Published: (2023)

Efficient reversal of transductions of sparse graph classes
by: Dreier, Jan, et al.
Published: (2026)

Some short notes on oriented line graphs and related matrices
by: Antony, Jacob, et al.
Published: (2025)

Oriented discrepancy of Hamilton cycles in oriented graphs satisfying Ore-type condition
by: Ai, Jiangdong, et al.
Published: (2025)

Counting the minimum number of arcs in an oriented graph having weak diameter 2
by: Das, Sandip, et al.
Published: (2023)

Max Weight Independent Set in sparse graphs with no long claws
by: Abrishami, Tara, et al.
Published: (2023)

Faster algorithms for graph homomorphism via tractable constraint satisfaction
by: Carbonnel, Clément
Published: (2026)

First order distinguishability of sparse random graphs
by: Hershko, Tal, et al.
Published: (2024)

First-order transducibility among classes of sparse graphs
by: Gajarský, Jakub, et al.
Published: (2025)

Designing sparse temporal graphs satisfying connectivity requirements
by: Bellitto, Thomas, et al.
Published: (2026)

Asymptotically faster algorithms for recognizing $(k,\ell)$-sparse graphs
by: Deák, Bence, et al.
Published: (2026)

Tree-layout based graph classes: proper chordal graphs
by: Paul, Christophe, et al.
Published: (2022)

Multipacking and broadcast domination on cactus graph and its impact on hyperbolic graph
by: Das, Sandip, et al.
Published: (2023)

Stereotype graph: A mathematical framework of category stereotypes via graph theory
by: Yan, Yijia
Published: (2025)

Fixed-parameter tractability and hardness for Steiner rooted and locally connected orientations
by: Bérczi, Kristóf, et al.
Published: (2025)