10 citations · 12 across the 9 of their papers we have counts for
8 papers · 1 filter
Space-Efficient Hierholzer for Undirected Graphs
Elena Grigorescu, Ziad Ismaili Alaoui, Tamio-Vesa Nakajima +2
We present a simple linear-time algorithm that outputs an Eulerian tour of an undirected multigraph with vertices and edges, if one exists, in time and using …
Virtual-Memory Powersort
Finn Moltmann, Tamio-Vesa Nakajima, Sebastian Wild
We give a more space-efficient implementation of adaptive mergesort: Virtual-Memory Powersort. Using internal buffering techniques, we significantly reduce the memory consumption o…
Rooting Out Entropy: Optimal Tree Extraction for Ultra-Succinct Graphs
Ziad Ismaili Alaoui, Tamio-Vesa Nakajima, Namrata +1
We combine two methods for the lossless compression of unlabeled graphs - entropy compressing adjacency lists and computing canonical names for vertices - and solve an ensuing nove…
Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa
Benjamin Bedert, Tamio-Vesa Nakajima, Karolina Okrasa +1
We introduce a new notion of sparsification, called \emph{strong sparsification}, in which constraints are not removed but variables can be merged. As our main result, we present a…
Maximum And- vs. Even-SAT
Tamio-Vesa Nakajima, Stanislav Živný
A multiset of literals, called a clause, is \emph{strongly satisfied} by an assignment if \emph{no} literal evaluates to false. Finding an assignment that maximises the number of s…
A Dichotomy for Maximum PCSPs on Graphs
Tamio-Vesa Nakajima, Stanislav Živný
Fix two non-empty loopless graphs and such that maps homomorphically to . The Maximum Promise Constraint Satisfaction Problem parameterised by and is the fol…
An approximation algorithm for Maximum DiCut vs. Cut
Tamio-Vesa Nakajima, Stanislav Živný
Goemans and Williamson designed a 0.878-approximation algorithm for Max-Cut in undirected graphs [JACM'95]. Khot, Kindler, Mosel, and O'Donnel showed that the approximation ratio o…
Maximum - vs. -colourings of graphs
Tamio-Vesa Nakajima, Stanislav Živný
We present polynomial-time SDP-based algorithms for the following problem: For fixed , given a real number and a graph that admits a -colouring with a …