We introduce and study the Generalized Cops and Robbers game (GCR), an
N-player pursuit game in graphs. The two-player version is essentially
equivalent to the classic Cops and Robbers (CR) game. The three-player version
can be understood as two CR games played simultaneously on the same graph; a
player can be at the same time both pursuer and evader. The same is true for
four or more players. We formulate GCR as a discounted stochastic game of
perfect information and prove that, for three or more players, it has at least
two Nash Equilibria: one in positional deterministic strategies and another in
non-positional ones. We also study the capturing properties of GCR Nash
Equilibria in connection to the cop-number of a graph. Finally, we briefly
discuss GCR as a member of a wider family of multi-player graph pursuit games
with rather interesting properties.

more |
pdf
| html
None.

360unfiltered:
RT @DO: Generalized Cops and Robbers: A Multi-Player Pursuit Game on Graphs. https://t.co/Xb1AhcYSUd

None.

None.

Sample Sizes : None.

Authors: 1

Total Words: 13144

Unqiue Words: 2012

We study shared processor scheduling of $\textit{multiprocessor}$ weighted
jobs where each job can be executed on its private processor and simultaneously
on possibly $\textit{many}$ processors shared by all jobs in order to reduce
their completion times due to processing time overlap. Each of $m$ shared
processors may charge different fee but otherwise the processors are identical.
The total weighted overlap of all jobs is to be maximized. This problem is key
to subcontractor scheduling in extended enterprises and supply chains, and
divisible load scheduling in computing. We prove that, quite surprisingly,
$\textit{synchronized}$ schedules that complete each job using shared
processors at the same time on its private and shared processors include
optimal schedules. We show that optimal $\alpha$-$\textit{private}$ schedules
that require each job to use its private processor for at least
$\alpha=1/2+1/(4(m+1))$ of the time required by the job guarantee more than an
$\alpha$ fraction of the total weighted overlap of the optimal...

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 15457

Unqiue Words: 2165

We study the weighted induced bipartite subgraph problem (WIBSP). The goal of
WIBSP is, given a graph and nonnegative weights for the nodes, to find a set W
of nodes with the maximum total weight such that a subgraph induced by W is
bipartite. WIBSP is also referred as to the graph bipartization problem or the
odd cycle transversal problem. In this paper, we show that WIBSP can be reduced
to the weighted independent set problem (WISP) where the number of nodes
becomes twice and the maximum degree increase by 1. WISP is a well-studied
combinatorial optimization problem. Thus, by using the reduction and results
about WISP, we can obtain nontrivial approximation and exact algorithms for
WIBSP.

more |
pdf
| html
None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 1665

Unqiue Words: 571

Recently, working on the Tanner graph which represents a low density parity
check (LDPC) code becomes an interesting research subject. Finding the number
of short cycles of Tanner graphs motivated Blake and Lin to investigate the
multiplicity of cycles of length girth in bi-regular bipartite graphs, by using
the spectrum and degree distribution of the graph. Although there were many
algorithms to find the number of cycles, they preferred to investigate in a
computational way. Dehghan and Banihashemi counted the number of cycles of
length $g+2$ and $g+4,$ where $G$ is a bi-regular bipartite graph and $g$ is
the length of the girth $G.$ But they just proposed a descriptive technique to
compute the multiplicity of cycles of length less than $2g$ for bi-regular
bipartite graphs. In this paper, we find the number of cycles of length less
than $2g$ by using spectrum and degree distribution of a bi-regular bipartite
graph such that the formula depends only on the partitions of positive integers
and the number of closed cycle-free walks...

more |
pdf
| html
None.

MathPaper:
Counting short cycles of (c,d)-regular bipartite graphs. https://t.co/tcxhs48tiM

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 6414

Unqiue Words: 1226

We investigate the 2-domination number for grid graphs, that is the size of a
smallest set $D$ of vertices of the grid such that each vertex of the grid
belongs to $D$ or has at least two neighbours in $D$. We give a closed formula
giving the 2-domination number of any $n \!\times\! m$ grid, hereby confirming
the known results (for $n \leq 5$). The proof relies on some dynamic
programming algorithms, using transfer matrices in (min,+)-algebra We also
apply the method to solve the Roman domination problem on grid graphs.

more |
pdf
| html
None.

MathPaper:
The 2-domination and Roman domination numbers of grid graphs. https://t.co/sbzNzVyAdC

MUKULBHALLA7:
https://t.co/ZwE26TBF9V

None.

None.

Sample Sizes : [2, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 2, 5]

Authors: 2

Total Words: 5893

Unqiue Words: 1303

Graphs are a central object of study in various scientific fields, such as
discrete mathematics, theoretical computer science and network science. These
graphs are typically studied using combinatorial, algebraic or probabilistic
methods, each of which highlights the properties of graphs in a unique way.
Here, we discuss a novel approach to study graphs: the simplex geometry (a
simplex is a generalized triangle). This perspective, proposed by Miroslav
Fiedler, introduces techniques from (simplex) geometry into the field of graph
theory and conversely, via an exact correspondence. We introduce this
graph-simplex correspondence, identify a number of basic connections between
graph characteristics and simplex properties, and suggest some applications as
example.

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 9330

Unqiue Words: 1928

Consider a random geometric graph over a random point process in
$\mathbb{R}^d$. Two points are connected by an edge if and only if their
distance is bounded by a prescribed distance parameter. We show that projecting
the graph onto a two dimensional plane is expected to yield a constant-factor
crossing number (and rectilinear crossing number) approximation. We also show
that the crossing number is positively correlated to the stress of the graph's
projection.

more |
pdf
| html
None.

MathPaper:
Crossing Numbers and Stress of Random Graphs. https://t.co/JjxoHHQsv3

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 8485

Unqiue Words: 1851

Recently, Fulek et al. have presented Hanani-Tutte results for (radial) level
planarity, i.e., a graph is (radial) level planar if it admits a (radial) level
drawing where any two (independent) edges cross an even number of times. We
show that the 2-Sat formulation of level planarity testing due to Randerath et
al. is equivalent to the strong Hanani-Tutte theorem for level planarity.
Further, we show that this relationship carries over to radial level planarity,
which yields a novel polynomial-time algorithm for testing radial level
planarity.

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 12791

Unqiue Words: 1787

This tutorial presents topological methods for the analysis and visualization
of scientific data from a user's perspective, with the Topology ToolKit (TTK),
a recently released open-source library for topological data analysis.
Topological methods have gained considerably in popularity and maturity over
the last twenty years and success stories of established methods have been
documented in a wide range of applications (combustion, chemistry,
astrophysics, material sciences, etc.) with both acquired and simulated data,
in both post-hoc and in-situ contexts. While reference textbooks have been
published on the topic, no tutorial at IEEE VIS has covered this area in recent
years, and never at a software level and from a user's point-of-view. This
tutorial fills this gap by providing a beginner's introduction to topological
methods for practitioners, researchers, students, and lecturers. In particular,
instead of focusing on theoretical aspects and algorithmic details, this
tutorial focuses on how topological methods can be useful in...

more |
pdf
| html
ballforest:
RT @arxiv_csgr: Topological Data Analysis Made Easy with the Topology ToolKit https://t.co/O5NtqBGijK

DA1KE:
RT @arxiv_cscv: Topological Data Analysis Made Easy with the Topology ToolKit https://t.co/TAWIKUcaak

None.

None.

Sample Sizes : None.

Authors: 11

Total Words: 3707

Unqiue Words: 1494

How to draw the vertices of a complete multipartite graph $G$ on different
points of a bounded $d$-dimensional integer grid, such that the sum of squared
distances between vertices of $G$ is (i) minimized or (ii) maximized? For both
problems we provide a characterization of the solutions. For the particular
case $d=1$, our solution for (i) also settles the minimum-2-sum problem for
complete bipartite graphs; the minimum-2-sum problem was defined by Juvan and
Mohar in 1992. Weighted centroidal Voronoi tessellations are the solution for
(ii). Such drawings are related with Laplacian eigenvalues of graphs. This
motivates us to study which properties of the algebraic connectivity of graphs
carry over to the restricted setting of drawings of graphs with integer
coordinates.

more |
pdf
| html
MathPaper:
Optimal Grid Drawings of Complete Multipartite Graphs and an Integer Variant of the Algebraic Connectivity. https://t.co/pipNKLewnZ

None.

None.

Sample Sizes : None.

Authors: 5

Total Words: 5758

Unqiue Words: 1374

Assert is a website where the best academic papers on arXiv (computer science, math, physics), bioRxiv (biology), BITSS (reproducibility), EarthArXiv (earth science), engrXiv (engineering), LawArXiv (law), PsyArXiv (psychology), SocArXiv (social science), and SportRxiv (sport research) bubble to the top each day.

Papers are scored (in real-time) based on how verifiable they are (as determined by their Github repos) and how interesting they are (based on Twitter).

To see top papers, follow us on twitter @assertpub_ (arXiv), @assert_pub (bioRxiv), and @assertpub_dev (everything else).

To see beautiful figures extracted from papers, follow us on Instagram.

*Tracking 72,893 papers.*

Sort results based on if they are interesting or reproducible.

Interesting

Reproducible