Výsledky vyhledávání - "Sawada, J. A."

Report

Concatenation trees: A framework for efficient universal cycle and de Bruijn sequence constructions

Autor: Sawada, J., Sears, J., Trautrim, A., Williams, A.

Classic cycle-joining techniques have found widespread application in creating universal cycles for a diverse range of combinatorial objects, such as shorthand permutations, weak orders, orientable sequences, and various subsets of $k$-ary strings, i

Externí odkaz: http://arxiv.org/abs/2308.12405

Zobrazit plný text záznamu

Report

A Pascal-like Bound for the Number of Necklaces with Fixed Density

Autor: Heckenberger, I., Sawada, J.

A bound resembling Pascal's identity is presented for binary necklaces with fixed density using Lyndon words with fixed density. The result is generalized to k-ary necklaces and Lyndon words with fixed content. The bound arises in the study of Nichol

Externí odkaz: http://arxiv.org/abs/1801.09516

Zobrazit plný text záznamu

Report

Deciding k-colourability of $P_5$-free graphs in polynomial time

Autor: Hoàng, Chính T., Kamiński, Marcin, Lozin, Vadim, Sawada, J., Shu, X.

The problem of computing the chromatic number of a $P_5$-free graph is known to be NP-hard. In contrast to this negative result, we show that determining whether or not a $P_5$-free graph admits a $k$-colouring, for each fixed number of colours $k$,

Externí odkaz: http://arxiv.org/abs/cs/0702043

Zobrazit plný text záznamu

Report

k-Colorability of P5-free graphs

Autor: Hoang, C. T., Sawada, J., Shu, X.

A polynomial time algorithm that determines for a fixed integer k whether or not a P5-free graph can be k-colored is presented in this paper. If such a coloring exists, the algorithm will produce a valid k-coloring.

Externí odkaz: http://arxiv.org/abs/cs/0609083

Zobrazit plný text záznamu