4 citations · 5 across the 13 of their papers we have counts for
17 papers
Rearrangements of distributions on integers that minimize variance
Aistis Atminas, Valentas Kurauskas
Which permutations of a probability distribution on integers minimize variance? Let be a random variable on a set of integers such that $\mathbb{P}(X_i =…
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…
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…
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…
Graph classes with linear Ramsey numbers
Bogdan Alecu, Aistis Atminas, Vadim Lozin +1
The Ramsey number for a class of graphs is the minimum such that every graph in with at least vertices has either a clique of size or an independent…
Graph functionality
Bogdan Alecu, Aistis Atminas, Vadim Lozin
Let be a graph and its adjacency matrix. We say that a vertex is a function of vertices if there exists a Boolean function of $…
Classes of graphs without star forests and related graphs
Aistis Atminas
This work provides a structural characterisation of hereditary graph classes that do not contain a star forest, several graphs obtained from star forests by subset complementation,…
Characterising inflations of monotone grid classes of permutations
Michael Albert, Aistis Atminas, Robert Brignall
We characterise those permutation classes whose simple permutations are monotone griddable. This characterisation is obtained by identifying a set of nine substructures, at least o…
On forbidden induced subgraphs for unit disk graphs
Aistis Atminas, Viktor Zamaraev
A unit disk graph is the intersection graph of disks of equal radii in the plane. The class of unit disk graphs is hereditary, and therefore admits a characterization in terms of m…
Well-quasi-ordering and finite distinguishing number
Aistis Atminas, Robert Brignall
Balogh, Bollobas and Weinreich showed that a parameter that has since been termed the distinguishing number can be used to identify a jump in the possible speeds of hereditary clas…
Minimal classes of graphs of unbounded clique-width defined by finitely many forbidden induced subgraphs
A. Atminas, R. Brignall, V. Lozin +1
We discover new hereditary classes of graphs that are minimal (with respect to set inclusion) of unbounded clique-width. The new examples include split permutation graphs and bicha…
Implicit Representations and Factorial Properties of Graphs
Aistis Atminas, Andrew Collins, Vadim Lozin +1
The idea of implicit representation of graphs was introduced in [S. Kannan, M. Naor, S. Rudich, Implicit representation of graphs, SIAM J. Discrete Mathematics, 5 (1992) 596--603]…
Graphs without large bicliques and well-quasi-orderability by the induced subgraph relation
Aistis Atminas, Vadim V. Lozin, Igor Razgon
Recently, Daligault, Rao and Thomassé asked in [3] if every hereditary class which is well-quasi-ordered by the induced subgraph relation is of bounded clique-width. There are two…
Scattered packings of cycles
Aistis Atminas, Marcin Kamiński, Jean-Florent Raymond
We consider the problem Scattered Cycles which, given a graph and two positive integers and , asks whether contains a collection of cycles that are pairwise a…
Deciding the Bell number for hereditary graph properties
Aistis Atminas, Andrew Collins, Jan Foniok +1
The paper [J. Balogh, B. Bollobás, D. Weinreich, A jump to the Bell number for hereditary graph properties, J. Combin. Theory Ser. B 95 (2005) 29--48] identifies a jump in the spee…
Well-Quasi-Order for Permutation Graphs Omitting a Path and a Clique
Aistis Atminas, Robert Brignall, Nicholas Korpelainen +2
We consider well-quasi-order for classes of permutation graphs which omit both a path and a clique. Our principle result is that the class of permutation graphs omitting and…
Universal graphs and universal permutations
Aistis Atminas, Sergey Kitaev, Vadim V. Lozin +1
Let be a family of graphs and the set of -vertex graphs in . A graph containing all graphs from as induced subgraphs is called -universal for …