BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Andrei Gagarin

Andrei Gagarin contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Discrete Mathematicsmath.COData Structures and AlgorithmsComputational Geometrymath.GT

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
10works
0followers
5topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

10 published item(s)

preprint2022arXiv

Embedding K3,3 and K5 on the Double Torus

The Kuratowski graphs $K_{3,3}$ and $K_5$ characterize planarity. Counting distinct 2-cell embeddings of these two graphs on orientable surfaces was previously done by using Burnside's Lemma and their automorphism groups, without actually constructing the embeddings. We obtain all 2-cell embeddings of these graphs on the double torus, using a constructive approach. This shows that there is a unique non-orientable 2-cell embedding of $K_{3,3}$, 14 orientable and 17 non-orientable 2-cell embeddings of $K_5$ on the double torus, which explicitly confirms the enumerative results. As a consequence, several new polygonal representations of the double torus are presented.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Pattern Backtracking Algorithm for the Workflow Satisfiability Problem

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 the assignment. (Such an assignment is called valid.) The problem is NP-hard even when restricted to the large class of user-independent constraints. Since the number of steps $k$ is relatively small in practice, it is natural to consider a parametrisation of the WSP by $k$. We propose a new fixed-parameter algorithm to solve the WSP with user-independent constraints. The assignments in our method are partitioned into equivalence classes such that the number of classes is exponential in $k$ only. We show that one can decide, in polynomial time, whether there is a valid assignment in an equivalence class. By exploiting this property, our algorithm reduces the search space to the space of equivalence classes, which it browses within a backtracking framework, hence emerging as an efficient yet relatively simple-to-implement or generalise solution method. We empirically evaluate our algorithm against the state-of-the-art methods and show that it clearly wins the competition on the whole range of our test problems and significantly extends the domain of practically solvable instances of the WSP.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Bounds and algorithms for limited packings in graphs

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(G)$, $\left|N[v] \cap X\right| \le k$, where $N[v]$ is the closed neighbourhood of $v$. The k-limited packing number $L_k(G)$ is the largest size of a k-limited packing in G. Limited packing problems can be considered as secure facility location problems in networks. We develop probabilistic and greedy approaches to limited packings in graphs, providing lower bounds for the k-limited packing number, and randomized and greedy algorithms to find k-limited packings satisfying the bounds. Some upper bounds for $L_k(G)$ are given as well. The problem of finding a maximum size k-limited packing is known to be NP-complete even in split or bipartite graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Iterative Plan Construction for the Workflow Satisfiability Problem

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 defined by business rules. We are required to decide whether there exists a \emph{plan} -- an assignment of tasks to authorized users -- such that all constraints are satisfied. Several bespoke algorithms have been constructed for solving the WSP, optimised to deal with constraints (business rules) of particular types. It is natural to see the WSP as a subclass of the {\em Constraint Satisfaction Problem (CSP)} in which the variables are tasks and the domain is the set of users. What makes the WSP distinctive as a CSP is that we can assume that the number of tasks is very small compared to the number of users. This is in sharp contrast with traditional CSP models where the domain is small and the number of variables is very large. As such, it is appropriate to ask for which constraint languages the WSP is fixed-parameter tractable (FPT), parameterized by the number of tasks. We have identified a new FPT constraint language, user-independent constraint, that includes many of the constraints of interest in business processing systems. We are also able to prove that the union of FPT languages remains FPT if they satisfy a simple compatibility condition. In this paper we present our generic algorithm, in which plans are grouped into equivalence classes, each class being associated with a \emph{pattern}. We demonstrate that our generic algorithm has running time $O^*(2^{k\log k})$, where $k$ is the number of tasks, for the language of user-independent constraints. We also show that there is no algorithm of running time $O^*(2^{o(k\log k)})$ for user-independent constraints unless the Exponential Time Hypothesis fails.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

The probabilistic approach to limited packings in graphs

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 $v\in V(G)$, $\left|N[v] \cap X\right| \le k$, where N[v] is the closed neighbourhood of v. The k-limited packing number $L_k(G)$ of a graph G is the largest size of a k-limited packing in G. Limited packing problems can be considered as secure facility location problems in networks. In this paper, we develop a new probabilistic approach to limited packings in graphs, resulting in lower bounds for the k-limited packing number and a randomized algorithm to find k-limited packings satisfying the bounds. In particular, we prove that for any graph G of order n with maximum vertex degree $Δ$, $$L_k(G) \ge {kn \over (k+1)\sqrt[k]{\pmatrix{Δ\cr k} (Δ+1)}}.$$ The problem of finding a maximum size k-limited packing is known to be NP-complete even in split or bipartite graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

The bondage number of graphs on topological surfaces and Teschner's conjecture

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 bondage number of graphs on topological surfaces, improve upper bounds for the bondage number in terms of the maximum vertex degree and the orientable and non-orientable genera of the graph, and show tight lower bounds for the number of vertices of graphs 2-cell embeddable on topological surfaces of a given genus. Also, we provide stronger upper bounds for graphs with no triangles and graphs with the number of vertices larger than a certain threshold in terms of the graph genera. This settles Teschner's Conjecture in positive for almost all graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv

Two-connected graphs with prescribed three-connected components

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 graph, we deduce from this decomposition a bicolored tree tc(g) associated with any 2-connected graph g, whose white vertices are the 3-components of g (3-connected components or polygons) and whose black vertices are bonds linking together these 3-components, arising from separating pairs of vertices of g. Two fundamental relationships on graphs and networks follow from this construction. The first one is a dissymmetry theorem which leads to the expression of the class B=B(F) of 2-connected graphs, all of whose 3-connected components belong to a given class F of 3-connected graphs, in terms of various rootings of B. The second one is a functional equation which characterizes the corresponding class R=R(F) of two-pole networks all of whose 3-connected components are in F. All the rootings of B are then expressed in terms of F and R. There follow corresponding identities for all the associated series, in particular the edge index series. Numerous enumerative consequences are discussed.

0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv

Upper bounds for alpha-domination parameters

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 same probabilistic construction is used to generalise another well-known upper bound for the classical domination in graphs. We also prove similar upper bounds for the alpha-rate domination number, which combines the concepts of alpha-domination and k-tuple domination.

0 citations0 reviewsNo code linkedOpen access
preprint2006arXiv

The structure and labelled enumeration of K_{3,3}-subdivision-free projective-planar graphs

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 decomposition as a graph K_5 (the core) where the edges are replaced by two-pole networks constructed from 2-connected planar graphs. A method to enumerate these graphs in the labelled case is described. Moreover, we enumerate the homeomorphically irreducible graphs in F and homeomorphically irreducible 2-connected planar graphs. Particular use is made of two-pole directed series-parallel networks. We also show that the number m of edges of graphs in F with n vertices satisfies the bound m <=3n-6, for n >= 6.

0 citations0 reviewsNo code linkedOpen access
preprint2005arXiv

The obstructions for toroidal graphs with no $K_{3,3}$&#39;s

Forbidden minors and subdivisions for toroidal graphs are numerous. We consider the toroidal graphs with no $K_{3,3}$-subdivisions that coincide with the toroidal graphs with no $K_{3,3}$-minors. These graphs admit a unique decomposition into planar components and have short lists of obstructions. We provide the complete lists of four forbidden minors and eleven forbidden subdivisions for the toroidal graphs with no $K_{3,3}$&#39;s and prove that the lists are sufficient.

0 citations0 reviewsNo code linkedOpen access