A. Atminas

activity

20132025

most citedMinimal classes of graphs of unbounded clique-width defined by finitely many forbidden induced subgraphs

4 citations · 5 across the 13 of their papers we have counts for

collaborators

17 papers

math.CO2025

Rearrangements of distributions on integers that minimize variance

Aistis Atminas, Valentas Kurauskas

Which permutations of a probability distribution on integers minimize variance? Let $X$ be a random variable on a set of integers ${x_{1}, \dots, x_{N}}$ such that $\mathbb{P}(X_i =…

math.CO2023

Graph parameters, implicit representations and factorial properties

Bogdan Alecu, Vladimir E. Alekseev, Aistis Atminas +2

How to efficiently represent a graph in computer memory is a fundamental data structuring question. In the present paper, we address this question from a combinatorial point of vie…

math.CO2022★ 1 cited

A dichotomy for graphs of bounded degeneracy

A. Atminas, V. Lozin

We prove that the degeneracy of graphs in a hereditary class defined by a finite set S of forbidden induced subgraphs is bounded if and only if S includes a complete graph, a compl…

math.CO2021

Combinatorics and algorithms for quasi-chain graphs

Bogdan Alecu, Aistis Atminas, Vadim Lozin +1

The class of quasi-chain graphs is an extension of the well-studied class of chain graphs. This latter class enjoys many nice and important properties, such as bounded clique-width…

math.CO2019

Graph classes with linear Ramsey numbers

Bogdan Alecu, Aistis Atminas, Vadim Lozin +1

The Ramsey number $R_{X} (p, q)$ for a class of graphs $X$ is the minimum $n$ such that every graph in $X$ with at least $n$ vertices has either a clique of size $p$ or an independent…

math.CO2018

Graph functionality

Bogdan Alecu, Aistis Atminas, Vadim Lozin

Let $G = (V, E)$ be a graph and $A$ its adjacency matrix. We say that a vertex $y \in V$ is a function of vertices $x_{1}, \dots, x_{k} \in V$ if there exists a Boolean function $f$ of $…