archive
Every paper Pith has read. Search by title, abstract, or pith.
398 papers in cs.DM · page 3
-
Greedy dueling sequence converges to Thue-Morse at specific rate
The speed of convergence in greedy Galois games
-
Two-graph model splits feasibility from movement in path discovery
Separating Feasibility and Movement in Solution Discovery: The Case of Path Discovery
-
Minimum temporal arcs for requests: n
Designing sparse temporal graphs satisfying connectivity requirements
-
-
Network design for potential flows solves via shortest paths
Approximating the Network Design Problem for Potential-Based Flows
-
Some d-regular digraphs exceed the conjectured cycle-factor maximum
Counterexamples to an Extremal Conjecture for Random Cycle-Factors
-
Counterexamples exceed conjectured cycle count in d-regular digraphs
Counterexamples to an Extremal Conjecture for Random Cycle-Factors
-
Size-4 Sidon sets fail to extend to perfect difference sets
Size-4 Counterexamples to the Sidon-Extension Conjecture
-
Size-4 Sidon sets fail to extend to perfect difference sets
Size-4 Counterexamples to the Sidon-Extension Conjecture
-
Polynomial kernels for leaf-constrained diverse spanning trees
Polynomial Kernels for Spanning Tree with Diversity Requirements
-
The paper constructs, for each integer h at least 4, a specific (2h-1)-uniform hypergraph…
Note on polychromatic coloring of hereditary hypergraph families II
-
Z-matrices with bipartite support obey Chollet's permanent inequality
On Chollet's Permanent Conjecture for Graph Laplacians
-
Any m-edge graph has permanental energy at least 2√m
Permanental Energy of Graphs
-
Lonely runner conjecture holds for ten to twelve runners
Eleven, twelve, and thirteen lonely runners
-
Harmonic numbers equal binomial sum for any nonzero m
A Proof of Bala's General-$m$ Representation of the Harmonic Numbers
-
Constructions give binary words with fewest abelian squares
Binary Words Containing Few Abelian Squares
-
Graph powers burn in at most sqrt(n/k) steps
Burning Graph Powers and Branching Trees
-
Branchwidth approximates submodular width to within 3/2
Cuts and Gauges for Submodular Width
-
Large digraphs reach k-arc-strength via exactly p-inversions
Increasing arc-connectivity by bounded- and fixed-size inversions
-
Rocq proof strengthens Sands-Sauer-Woodrow theorem
A formal proof of the Sands-Sauer-Woodrow theorem using the Rocq prover and mathcomp/ssreflect
-
Rainbow matching is poly-time if most color classes are multipartite
A Complexity Dichotomy for Generalized Rainbow Matchings Based on Color Classes
-
Isabelle/HOL library encodes primal-dual proofs for algorithms
Formal Primal-Dual Algorithm Analysis
-
Every graph is a threshold-PCG with n factors but fixed factors are rare
On Threshold Compatibility Graphs
-
One edge fix fails to remove all extreme-weight perfect matchings
A hierarchy of edge-weight symmetries in perfect matchings
-
Completely independent Steiner trees ensure dual-disjoint paths for terminals
Completely Independent Steiner Trees
-
Reduced component max-leaf bridges clique-width and bandwidth
Moderately beyond clique-width: reduced component max-leaf and related parameters
-
Reentrant flow shops reduce exactly to parallel machines with arrivals
Flow Shop Scheduling with Stochastic Reentry
-
Degree at least 2n/3 connects perfect matchings by two-edge switches
Dirac's theorem and the switch geometry of perfect matchings
-
SDP hyperplane sampling hits 0.878 ratio for max-cut and fractional covers
Maximum Cuts and Fractional Cut Covers: A Computational Study of a Randomized Semidefinite Programming Approach
-
Laplacian polynomials derived for power graphs of pqr-order groups
On (distance) Laplacian characteristic polynomials of power graphs
-
Rado constant for high-d balls: between 3^{-d} and 2.447^{-d}
Rado's covering problem for cubes and balls: a semi-survey
-
Rooted metric polytope volume greatly exceeds elliptope on complete graphs
On the volume of the elliptope and related metric polytopes
-
Nested rational points force equal quadrics over finite fields
Maximal quadrics over finite fields and minimal codewords of projective Reed-Muller codes
-
Patterns in small cases fix ordered Ramsey numbers for graph classes
Some results on small ordered and cyclic Ramsey numbers
-
Halfspace separation solvable in polynomial time for three graph classes
Halfspace separation in geodesic convexity
-
Online Ramsey numbers for paths and stars grow linearly with n
On the asymptotic behavior of online Ramsey numbers for stars, paths and cycles
-
Hypercube 4-neighbor bootstrap matches lower bound infinitely often
Optimal and Near-Optimal Constructions for Bootstrap Percolation in Hypercubes
-
Random k-ary chains decompress with e^{c sqrt n} size factor
The decompressed tree size of $k$-ary chains
-
The paper develops new techniques for embedding word structures from Euclidean Bianchi…
On Word Representations and Embeddings in Complex Matrices
-
Algorithm matches conjectured O(sqrt(d)) Steinitz bound
Near-Optimal Constructive Bounds for $\ell_2$ Prefix Discrepancy and Steinitz Problems via Affine Spectral Independence
-
Faster algorithms check (k,ℓ)-sparsity in subquadratic time
Asymptotically faster algorithms for recognizing $(k,\ell)$-sparse graphs
-
VC-bounded graphs allow εn² GED approximation in n^{O(d/ε²)} time
Robust Graph Isomorphism, Quadratic Assignment and VC Dimension
-
0-1 edge weights for distinct vertex sums are hard by feedback vertex set
The Parameterized Complexity of Vertex-Coloring Edge-Weighting
-
Glauber dynamics mixes in O(n log n) for colorings with (1+δ)Δ colors
Sampling Colorings Close to the Maximum Degree: Non-Markovian Coupling and Local Uniformity
-
Fat-minor-free graphs admit coarsely small balanced separators
Coarse Balanced Separators in Fat-Minor-Free Graphs
-
Exact closeness formulas derived for middle graphs under vertex failures
Analyzing Network Robustness via Residual Closeness
-
Color classes bound distance Laplacian eigenvalues
Extremal chromatic bounds for distance Laplacian eigenvalues
-
Color class sizes bound distance Laplacian eigenvalues
Extremal chromatic bounds for distance Laplacian eigenvalues
-
New upper bound on edges in k-crown-free linear r-graphs
An Upper Bound on the Linear Tur\'{a}n Number of $k$-Crowns
-
Boolean network attractors factor into module products
Strong modules and asynchronous attractors of Boolean networks