Discrete Mathematics

Authors and titles for cs.DM in Mar 2024

[1]  arXiv:2403.02026 [pdf, other]

Title: Graph drawing applications in combinatorial theory of maturity models

Authors: Špela Kajzer, Alexander Dobler, Janja Jerebic, Martin Nöllenburg, Joachim Orthaber, Drago Bokal

Comments: 39 pages, 12 figures

Subjects: Discrete Mathematics (cs.DM)

[2]  arXiv:2403.02198 [pdf, ps, other]

Title: Payment Scheduling in the Interval Debt Model

Authors: Tom Friedetzky, David C. Kutner, George B. Mertzios, Iain A. Stewart, Amitabh Trehan

Comments: 30 pages, 17 figures

Subjects: Discrete Mathematics (cs.DM); Computational Complexity (cs.CC); Computational Engineering, Finance, and Science (cs.CE)

[3]  arXiv:2403.04777 [pdf, other]

Title: Specifying and Verifying the Convergence Stairs of the Collatz Program

Authors: Ali Ebnenasir

Subjects: Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS); Formal Languages and Automata Theory (cs.FL)

[4]  arXiv:2403.06691 [pdf, other]

Title: Approximating Maximum Edge 2-Coloring by Normalizing Graphs

Authors: Tobias Mömke, Alexandru Popa, Aida Roshany-Tabrizi, Michael Ruderer, Roland Vincze

Comments: 20 pages, 6 figures, preliminary version published at WAOA 2023

Subjects: Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS)

[5]  arXiv:2403.08534 [pdf, ps, other]

Title: Ensuring connectedness for the Maximum Quasi-clique and Densest $k$-subgraph problems

Authors: Daniela Scherer dos Santos, Kathrin Klamroth, Pedro Martins, Luís Paquete

Subjects: Discrete Mathematics (cs.DM)

[6]  arXiv:2403.08703 [pdf, other]

Title: Improved Dynamics for the Maximum Common Subgraph Problem

Authors: Davide Guidobene, Guido Cera

Comments: 6 pages, 5 figures

Subjects: Discrete Mathematics (cs.DM)

[7]  arXiv:2403.08921 [pdf, ps, other]

Title: On sampling diluted Spin Glasses using Glauber dynamics

Authors: Charilaos Efthymiou, Kostas Zampetakis

Comments: 44 pages

Subjects: Discrete Mathematics (cs.DM); Probability (math.PR)

[8]  arXiv:2403.09122 [pdf, ps, other]

Title: Bounds and extremal graphs for monitoring edge-geodetic sets in graphs

Authors: Florent Foucaud, Pierre-Marie Marcille, Zin Mar Myint, R.B. Sandeep, Sagnik Sen, S. Taruni

Subjects: Discrete Mathematics (cs.DM); Combinatorics (math.CO)

[9]  arXiv:2403.09311 [pdf, other]

Title: Binary Stretch Embedding of Weighted Graphs

Authors: Javad B. Ebrahimi, Mehri Oghbaei Bonab

Subjects: Discrete Mathematics (cs.DM); Combinatorics (math.CO)

[10]  arXiv:2403.10896 [pdf, ps, other]

Title: Solving the Multiobjective Quasi-Clique Problem

Authors: Daniela Scherer dos Santos, Kathrin Klamroth, Pedro Martins, Luís Paquete

Subjects: Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS)

[11]  arXiv:2403.11779 [pdf, other]

Title: Home Spaces and Invariants to Analyze Parameterized Petri Nets

Authors: Gerard Memmi

Comments: 20 pages. arXiv admin note: substantial text overlap with arXiv:2306.07623

Subjects: Discrete Mathematics (cs.DM); Logic in Computer Science (cs.LO)

[12]  arXiv:2403.12581 [pdf, ps, other]

Title: An Upper Bound on the Weisfeiler-Leman Dimension

Authors: Thomas Schneider, Pascal Schweitzer

Subjects: Discrete Mathematics (cs.DM); Logic in Computer Science (cs.LO); Combinatorics (math.CO)

[13]  arXiv:2403.12705 [pdf, other]

Title: The ultrametric backbone is the union of all minimum spanning forests

Authors: Jordan C Rozum, Luis M Rocha

Comments: 10 pages, 1 figure. Revision corrects typo in abstract

Subjects: Discrete Mathematics (cs.DM)

[14]  arXiv:2403.15215 [pdf, other]

Title: Exploring the Crochemore and Ziv-Lempel factorizations of some automatic sequences with the software Walnut

Authors: Marieh Jahannia, Manon Stipulanti

Comments: 15 pages, 2 figures

Subjects: Discrete Mathematics (cs.DM); Combinatorics (math.CO)

[15]  arXiv:2403.16983 [pdf, other]

Title: Robust Filter Design for Graph Signals

Authors: Lucia Testa, Stefania Sardellitti, Sergio Barbarossa

Subjects: Discrete Mathematics (cs.DM)

[16]  arXiv:2403.17969 [pdf, other]

Title: Antimagic Labeling of Graphs Using Prime Numbers

Authors: Arafat Islam, Md. Imtiaz Habib

Comments: 11 pages, 15 figures

Subjects: Discrete Mathematics (cs.DM); Combinatorics (math.CO)

[17]  arXiv:2403.00115 (cross-list from cs.CC) [pdf, ps, other]

Title: PosSLP and Sum of Squares

Authors: Markus Bläser, Julian Dörfler, Gorav Jindal

Subjects: Computational Complexity (cs.CC); Discrete Mathematics (cs.DM)

[18]  arXiv:2403.00598 (cross-list from cs.GT) [pdf, ps, other]

Title: Popularity and Perfectness in One-sided Matching Markets with Capacities

Authors: Gergely Csáji

Subjects: Computer Science and Game Theory (cs.GT); Discrete Mathematics (cs.DM)

[19]  arXiv:2403.01662 (cross-list from cs.CC) [pdf, ps, other]

Title: Atropos-k is PSPACE-complete

Authors: Chao Yang, Zhujun Zhang

Subjects: Computational Complexity (cs.CC); Discrete Mathematics (cs.DM); Combinatorics (math.CO)

[20]  arXiv:2403.02140 (cross-list from cs.DS) [pdf, other]

Title: Matching Algorithms in the Sparse Stochastic Block Model

Authors: Anna Brandenberger, Byron Chin, Nathan S. Sheffield, Divya Shyamal

Comments: 28 pages

Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM)

[21]  arXiv:2403.03504 (cross-list from cs.DS) [pdf, other]

Title: Graph Visualization for Blockchain Data

Authors: Marcell Dietl, Andre Gemünd, Daniel Oeltz, Felix M. Thiele, Christian Werner

Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM)

[22]  arXiv:2403.03696 (cross-list from cs.DS) [pdf, ps, other]

Title: Largest common subgraph of two forests

Authors: Dieter Rautenbach, Florian Werner

Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM); Combinatorics (math.CO)

[23]  arXiv:2403.03830 (cross-list from cs.DS) [pdf, other]

Title: Parameterized Algorithms for Balanced Cluster Edge Modification Problems

Authors: Jayakrishnan Madathil, Kitty Meeks

Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM)

[24]  arXiv:2403.04589 (cross-list from cs.DS) [pdf, ps, other]

Title: Algorithms and complexity for path covers of temporal DAGs: when is Dilworth dynamic?

Authors: Dibyayan Chakraborty, Antoine Dailly, Florent Foucaud, Ralf Klasing

Comments: 21 pages

Subjects: Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM); Combinatorics (math.CO)

[25]  arXiv:2403.05749 (cross-list from eess.SY) [pdf, other]

Title: Characterizing Flow Complexity in Transportation Networks using Graph Homology

Authors: Shashank A Deshpande, Hamsa Balakrishnan

Comments: 7 pages, 3 figures, letter

Subjects: Systems and Control (eess.SY); Discrete Mathematics (cs.DM)