4 papers
NP-complete variants of some classical graph problems
Per Alexandersson
Some classical graph problems such as finding minimal spanning tree, shortest path or maximal flow can be done efficiently. We describe slight variations of such problems which are…
LaserTank is NP-complete
Per Alexandersson, Petter Restadh
We show that the classical game LaserTank is -complete, even when the tank movement is restricted to a single column and the only blocks appearing on the board are mir…
The cyclic sieving phenomenon on circular Dyck paths
Per Alexandersson, Svante Linusson, Samu Potka
We give a -enumeration of circular Dyck paths, which is a superset of the classical Dyck paths enumerated by the Catalan numbers. These objects have recently been studied by Ale…
LLT polynomials, elementary symmetric functions and melting lollipops
Per Alexandersson
We conjecture an explicit positive combinatorial formula for the expansion of unicellular LLT polynomials in the elementary symmetric basis. This is an analogue of the Shareshian-W…