24 citations · 166 across the 22 of their papers we have counts for
23 papers
Approximation algorithms and ratios for multiple domination in graphs
Lukas Dijkstra, Vadim Zverovich, Andrei Gagarin
We analyse approximation algorithms (greedy heuristics) for the classical domination number and two multiple domination numbers in simple graphs. First, we present a short self-con…
Greedy and randomized heuristics for optimization of k-domination models in digraphs and road networks
Lukas Dijkstra, Andrei Gagarin, Padraig Corcoran +1
Directed graphs provide more subtle and precise modelling tools for optimization in road networks than simple graphs. In particular, they are more suitable in the context of altern…
Embedding K3,3 and K5 on the Double Torus
William L. Kocay, Andrei Gagarin
The Kuratowski graphs and characterize planarity. Counting distinct 2-cell embeddings of these two graphs on orientable surfaces was previously done by using Burnsi…
Weighted domination models and randomized heuristics
Lukas Dijkstra, Andrei Gagarin, Vadim Zverovich
We consider the minimum weight and smallest weight minimum-size dominating set problems in vertex-weighted graphs and networks. The latter problem is a two-objective optimization p…
Heuristics for k-domination models of facility location problems in street networks
Padraig Corcoran, Andrei Gagarin
We present new greedy and beam search heuristic methods to find small-size -dominating sets in graphs. The methods are inspired by a new problem formulation which explicitly hig…
Multiple domination models for placement of electric vehicle charging stations in road networks
Padraig Corcoran, Andrei Gagarin
Electric and hybrid vehicles play an increasing role in the road transport networks. Despite their advantages, they have a relatively limited cruising range in comparison to tradit…
Pattern-Based Approach to the Workflow Satisfiability Problem with User-Independent Constraints
Daniel Karapetyan, Andrew J. Parkes, Gregory Gutin +1
The fixed parameter tractable (FPT) approach is a powerful tool in tackling computationally hard problems. In this paper, we link FPT results to classic artificial intelligence (AI…
The complement of proper power graphs of finite groups
T. Anitha, R. Rajkumar, Andrei Gagarin
For a finite group , the proper power graph of is the graph whose vertices are non-trivial elements of and two vertices and are adjacent if an…
Classification of finite groups with toroidal or projective-planar permutability graphs
R. Rajkumar, P. Devi, Andrei Gagarin
Let be a group. The permutability graph of subgroups of , denoted by , is a graph having all the proper subgroups of as its vertices, and two subgroups are adjacen…
Algorithms for the workflow satisfiability problem engineered for counting constraints
D. Cohen, J. Crampton, A. Gagarin +2
The workflow satisfiability problem (WSP) asks whether there exists an assignment of authorized users to the steps in a workflow specification that satisfies the constraints in the…
On the Workflow Satisfiability Problem with Class-Independent Constraints
Jason Crampton, Andrei Gagarin, Gregory Gutin +2
A workflow specification defines sets of steps and users. An authorization policy determines for each user a subset of steps the user is allowed to perform. Other security requirem…
Pattern Backtracking Algorithm for the Workflow Satisfiability Problem
Daniel Karapetyan, Andrei Gagarin, Gregory Gutin
The workflow satisfiability problem (WSP) asks whether there exists an assignment of authorised users to the steps in a workflow specification, subject to certain constraints on th…
Bounds and algorithms for limited packings in graphs
Andrei Gagarin, Vadim Zverovich
We consider (closed neighbourhood) packings and their generalization in graphs called limited packings. A vertex set X in a graph G is a k-limited packing if for any vertex $v\in V…
The probabilistic approach to limited packings in graphs
Andrei Gagarin, Vadim Zverovich
We consider (closed neighbourhood) packings and their generalization in graphs. A vertex set X in a graph G is a k-limited packing if for any vertex , $\left|N[v] \cap X…
Iterative Plan Construction for the Workflow Satisfiability Problem
David Cohen, Jason Crampton, Andrei Gagarin +2
The \emph{Workflow Satisfiability Problem (WSP)} is a problem of practical interest that arises whenever tasks need to be performed by authorized users, subject to constraints defi…
The bondage number of graphs on topological surfaces and Teschner's conjecture
Andrei Gagarin, Vadim Zverovich
The bondage number of a graph is the smallest number of its edges whose removal results in a graph having a larger domination number. We provide constant upper bounds for the bonda…
Upper bounds for the bondage number of graphs on topological surfaces
Andrei Gagarin, Vadim Zverovich
The bondage number b(G) of a graph G is the smallest number of edges of G whose removal from G results in a graph having the domination number larger than that of G. We show that,…
Upper bounds for alpha-domination parameters
Andrei Gagarin, Anush Poghosyan, Vadim E. Zverovich
In this paper, we provide a new upper bound for the alpha-domination number. This result generalises the well-known Caro-Roditty bound for the domination number of a graph. The sam…
Two-connected graphs with prescribed three-connected components
Andrei Gagarin, Gilbert Labelle, Pierre Leroux +1
We adapt the classical 3-decomposition of any 2-connected graph to the case of simple graphs (no loops or multiple edges). By analogy with the block-cutpoint tree of a connected gr…
Counting unlabelled toroidal graphs with no K33-subdivisions
Andrei Gagarin, Gilbert Labelle, Pierre Leroux
We provide a description of unlabelled enumeration techniques, with complete proofs, for graphs that can be canonically obtained by substituting 2-pole networks for the edges of co…
Characterization and enumeration of toroidal K_{3,3}-subdivision-free graphs
Andrei Gagarin, Gilbert Labelle, Pierre Leroux
We describe the structure of 2-connected non-planar toroidal graphs with no K_{3,3}-subdivisions, using an appropriate substitution of planar networks into the edges of certain gra…
The obstructions for toroidal graphs with no 's
Andrei Gagarin, Wendy Myrvold, John Chambers
Forbidden minors and subdivisions for toroidal graphs are numerous. We consider the toroidal graphs with no -subdivisions that coincide with the toroidal graphs with no $K…
The structure and labelled enumeration of K_{3,3}-subdivision-free projective-planar graphs
Andrei Gagarin, Gilbert Labelle, Pierre Leroux
We consider the class F of 2-connected non-planar K_{3,3}-subdivision-free graphs that are embeddable in the projective plane. We show that these graphs admit a unique decompositio…