Top 10 Arxiv Papers Today in Discrete Mathematics


0.0 Mikeys
#1. Generalized Cops and Robbers: A Multi-Player Pursuit Game on Graphs
Athanasios Kehagias
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
Figures
None.
Tweets
360unfiltered: RT @DO: Generalized Cops and Robbers: A Multi-Player Pursuit Game on Graphs. https://t.co/Xb1AhcYSUd
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 13144
Unqiue Words: 2012

0.0 Mikeys
#2. Shared Processor Scheduling of Multiprocessor Jobs
Dariusz Dereniowski, Wieslaw Kubiak
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
Figures
None.
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 15457
Unqiue Words: 2165

0.0 Mikeys
#3. On a reduction of the weighted induced bipartite subgraph problem to the weighted independent set problem
Yotaro Takazawa, Shinji Mizuno
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
Figures
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 1665
Unqiue Words: 571

0.0 Mikeys
#4. Counting short cycles of (c,d)-regular bipartite graphs
Mohsen Alinejad, Kazem Khashyarmanesh
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
Figures
None.
Tweets
MathPaper: Counting short cycles of (c,d)-regular bipartite graphs. https://t.co/tcxhs48tiM
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 6414
Unqiue Words: 1226

0.0 Mikeys
#5. The 2-domination and Roman domination numbers of grid graphs
Michaël Rao, Alexandre Talon
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
Figures
None.
Tweets
MathPaper: The 2-domination and Roman domination numbers of grid graphs. https://t.co/sbzNzVyAdC
MUKULBHALLA7: https://t.co/ZwE26TBF9V
Github
None.
Youtube
None.
Other stats
Sample Sizes : [2, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 2, 5]
Authors: 2
Total Words: 5893
Unqiue Words: 1303

0.0 Mikeys
#6. The Simplex Geometry of Graphs
Karel Devriendt, Piet Van Mieghem
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
Figures
None.
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 9330
Unqiue Words: 1928

0.0 Mikeys
#7. Crossing Numbers and Stress of Random Graphs
Markus Chimani, Hanna Döring, Matthias Reitzner
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
Figures
None.
Tweets
MathPaper: Crossing Numbers and Stress of Random Graphs. https://t.co/JjxoHHQsv3
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 8485
Unqiue Words: 1851

0.0 Mikeys
#8. Level Planarity: Transitivity vs. Even Crossings
Guido Brückner, Ignaz Rutter, Peter Stumpf
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
Figures
None.
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 12791
Unqiue Words: 1787

0.0 Mikeys
#9. Topological Data Analysis Made Easy with the Topology ToolKit
Guillaume Favelier, Charles Gueunet, Attila Gyulassy, Julien Kitware, Joshua Levine, Jonas Lukasczyk, Daisuke Sakurai, Maxime Soler, Julien Tierny, Will Usher, Qi Wu
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
Figures
Tweets
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
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 11
Total Words: 3707
Unqiue Words: 1494

0.0 Mikeys
#10. Optimal Grid Drawings of Complete Multipartite Graphs and an Integer Variant of the Algebraic Connectivity
Ruy Fabila-Monroy, Carlos Hidalgo-Toscano, Clemens Huemer, Dolores Lara, Dieter Mitsche
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
Figures
Tweets
MathPaper: Optimal Grid Drawings of Complete Multipartite Graphs and an Integer Variant of the Algebraic Connectivity. https://t.co/pipNKLewnZ
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 5
Total Words: 5758
Unqiue Words: 1374

About

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.

Search
Sort results based on if they are interesting or reproducible.
Interesting
Reproducible
Categories
All
Astrophysics
Cosmology and Nongalactic Astrophysics
Earth and Planetary Astrophysics
Astrophysics of Galaxies
High Energy Astrophysical Phenomena
Instrumentation and Methods for Astrophysics
Solar and Stellar Astrophysics
Condensed Matter
Disordered Systems and Neural Networks
Mesoscale and Nanoscale Physics
Materials Science
Other Condensed Matter
Quantum Gases
Soft Condensed Matter
Statistical Mechanics
Strongly Correlated Electrons
Superconductivity
Computer Science
Artificial Intelligence
Hardware Architecture
Computational Complexity
Computational Engineering, Finance, and Science
Computational Geometry
Computation and Language
Cryptography and Security
Computer Vision and Pattern Recognition
Computers and Society
Databases
Distributed, Parallel, and Cluster Computing
Digital Libraries
Discrete Mathematics
Data Structures and Algorithms
Emerging Technologies
Formal Languages and Automata Theory
General Literature
Graphics
Computer Science and Game Theory
Human-Computer Interaction
Information Retrieval
Information Theory
Machine Learning
Logic in Computer Science
Multiagent Systems
Multimedia
Mathematical Software
Numerical Analysis
Neural and Evolutionary Computing
Networking and Internet Architecture
Other Computer Science
Operating Systems
Performance
Programming Languages
Robotics
Symbolic Computation
Sound
Software Engineering
Social and Information Networks
Systems and Control
Economics
Econometrics
General Economics
Theoretical Economics
Electrical Engineering and Systems Science
Audio and Speech Processing
Image and Video Processing
Signal Processing
General Relativity and Quantum Cosmology
General Relativity and Quantum Cosmology
High Energy Physics - Experiment
High Energy Physics - Experiment
High Energy Physics - Lattice
High Energy Physics - Lattice
High Energy Physics - Phenomenology
High Energy Physics - Phenomenology
High Energy Physics - Theory
High Energy Physics - Theory
Mathematics
Commutative Algebra
Algebraic Geometry
Analysis of PDEs
Algebraic Topology
Classical Analysis and ODEs
Combinatorics
Category Theory
Complex Variables
Differential Geometry
Dynamical Systems
Functional Analysis
General Mathematics
General Topology
Group Theory
Geometric Topology
History and Overview
Information Theory
K-Theory and Homology
Logic
Metric Geometry
Mathematical Physics
Numerical Analysis
Number Theory
Operator Algebras
Optimization and Control
Probability
Quantum Algebra
Rings and Algebras
Representation Theory
Symplectic Geometry
Spectral Theory
Statistics Theory
Mathematical Physics
Mathematical Physics
Nonlinear Sciences
Adaptation and Self-Organizing Systems
Chaotic Dynamics
Cellular Automata and Lattice Gases
Pattern Formation and Solitons
Exactly Solvable and Integrable Systems
Nuclear Experiment
Nuclear Experiment
Nuclear Theory
Nuclear Theory
Physics
Accelerator Physics
Atmospheric and Oceanic Physics
Applied Physics
Atomic and Molecular Clusters
Atomic Physics
Biological Physics
Chemical Physics
Classical Physics
Computational Physics
Data Analysis, Statistics and Probability
Physics Education
Fluid Dynamics
General Physics
Geophysics
History and Philosophy of Physics
Instrumentation and Detectors
Medical Physics
Optics
Plasma Physics
Popular Physics
Physics and Society
Space Physics
Quantitative Biology
Biomolecules
Cell Behavior
Genomics
Molecular Networks
Neurons and Cognition
Other Quantitative Biology
Populations and Evolution
Quantitative Methods
Subcellular Processes
Tissues and Organs
Quantitative Finance
Computational Finance
Economics
General Finance
Mathematical Finance
Portfolio Management
Pricing of Securities
Risk Management
Statistical Finance
Trading and Market Microstructure
Quantum Physics
Quantum Physics
Statistics
Applications
Computation
Methodology
Machine Learning
Other Statistics
Statistics Theory
Feedback
Online
Stats
Tracking 72,893 papers.