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

Vadim Zverovich

Vadim Zverovich contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.CODiscrete MathematicsComputer Science and Game Theory

Trust snapshot

Quick read

Trust 17 - UnverifiedVerification L1Unclaimed author
4works
0followers
3topics
2close 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

4 published item(s)

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
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

Braess' Paradox in a Generalised Traffic Network

The classical network configuration introduced by Braess in 1968 is of fundamental significance because Valiant and Roughgarden showed in 2006 that `the "global" behaviour of an equilibrium flow in a large random network is similar to that in Braess' original four-node example'. In this paper, a natural generalisation of Braess' network is introduced and conditions for the occurrence of Braess' paradox are formulated for the generalised network. The Braess' paradox has been studied mainly in the context of the classical problem introduced by Braess and his colleagues, assuming a certain type of networks. Specifically, two pairs of links in those networks are assumed to have the same volume-delay functions. The occurrence of Braess' paradox for this specific case of network symmetry was investigated by Pas and Principio in 1997. Such a symmetry is not common in real-life networks because the parameters of volume-delay functions are associated with roads physical and functional characteristics, which typically differ from one link to another (e.g. roads in networks are of different length). Our research provides an extension of previous studies on Braess' paradox by considering arbitrary volume-delay functions, i.e. symmetry properties are not assumed for any of the network's links and the occurrence of Braess' paradox is studied for a general configuration.

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