Cover Image

Complexity and algorithms for Arc-Kayles and Non-Disconnecting Arc-Kayles

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Burke, Kyle, Dailly, Antoine, Oijid, Nacim
Format:	Preprint
Published:	2024
Subjects:	Combinatorics Discrete Mathematics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A generalization of Arc-Kayles
by: Dailly, Antoine, et al.
Published: (2017)

Misère Partizan Arc Kayles is PSPACE-complete, even on Planar Graphs
by: Burke, Kyle, et al.
Published: (2025)

Bounded degree QBF and positional games
by: Oijid, Nacim
Published: (2024)

Exact number of flips required to sort a burnt stack of pancakes
by: Jäger, Gerold, et al.
Published: (2026)

On the complexity of the Maker-Breaker happy vertex game
by: Hilaire, Mathieu, et al.
Published: (2026)

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

Token positional games
by: Bagan, Guillaume, et al.
Published: (2026)

On the parameterized complexity of the Maker-Breaker domination game
by: Bagan, Guillaume, et al.
Published: (2026)

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

Connected Subtraction Games on Subdivided Stars
by: Dailly, Antoine, et al.
Published: (2018)

Strengthening the Murty-Simon conjecture on diameter 2 critical graphs
by: Dailly, Antoine, et al.
Published: (2018)

On the balanceability of some graph classes
by: Dailly, Antoine, et al.
Published: (2020)

Feedback Arc Sets and Feedback Arc Set Decompositions in Weighted and Unweighted Oriented Graphs
by: Gutin, Gregory, et al.
Published: (2025)

Graph Irregularity via Edge Deletions
by: Bensmail, Julien, et al.
Published: (2025)

Reconstructing graphs with subgraph compositions
by: Dailly, Antoine, et al.
Published: (2025)

A two-player version of the assignment problem
by: Galliot, Florian, et al.
Published: (2026)

Neighbour sum distinguishing edge-weightings with local constraints
by: Dailly, Antoine, et al.
Published: (2022)

Partition games
by: Dailly, Antoine, et al.
Published: (2018)

Largest planar graphs of diameter $3$ and fixed maximum degree -- connection with fractional matchings
by: Dailly, Antoine, et al.
Published: (2025)

A Vizing-like theorem for union vertex-distinguishing edge coloring
by: Bousquet, Nicolas, et al.
Published: (2016)

Fast winning strategies for the attacker in eternal domination
by: Bagan, Guillaume, et al.
Published: (2024)

An Algorithm for Monitoring Edge-geodetic Sets in Chordal Graphs
by: Marcille, Clara, et al.
Published: (2026)

Octal Games on Graphs: The game 0.33 on subdivided stars and bistars
by: Beaudou, Laurent, et al.
Published: (2016)

Algorithms and complexity for path covers of temporal DAGs: when is Dilworth dynamic?
by: Chakraborty, Dibyayan, et al.
Published: (2024)

Poset Positional Games
by: Bagan, Guillaume, et al.
Published: (2024)

The Non-Cancelling Intersections Conjecture
by: Amarilli, Antoine, et al.
Published: (2024)

Extending Robinson Spaces: Complexity and Algorithmic Solutions for Non-Symmetric Dissimilarity Spaces
by: Brucker, Francois, et al.
Published: (2024)

Resolving Sets in Temporal Graphs
by: Bok, Jan, et al.
Published: (2024)

Variants of Wythoff game with terminal positions or blocking maneuvers
by: Renard, Antoine, et al.
Published: (2025)

Karp's patching algorithm on dense digraph
by: Frieze, Alan
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)

On Iiro Honkala's contributions to identifying codes
by: Hudry, Olivier, et al.
Published: (2024)

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

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

A Note on the Complexity of Graph Recoloring
by: Bousquet, Nicolas
Published: (2024)

Node-Kayles on Trees
by: Songsuwan, Nuttanon
Published: (2025)

Line Graphs of Non-Word-Representable Graphs are Not Always Non-Word-Representable
by: Mozhui, Khyodeno, et al.
Published: (2025)

On the Identity and Group Problems for Complex Heisenberg Matrices
by: Bell, Paul C., et al.
Published: (2023)

Non-dissective coverings by planks
by: Kupavskii, Andrey, et al.
Published: (2025)