archive
Every paper Pith has read. Search by title, abstract, or pith.
398 papers in cs.DM · page 4
-
OPI admits solutions better than DQI semicircle law
On Worst-Case Optimal Polynomial Intersection
-
Random 0/1-polytopes expand at linear rate in n
Random 0/1-polytopes expand rapidly
-
Friendship graphs' domination polynomials have three real zeros
On roots of domination polynomials for friendship and book graphs
-
Color coding counts hypergraphlets faster on (α,β)-nice hypergraphs
Counting HyperGraphlets via Color Coding: a Quadratic Barrier and How to Break It
-
Sparse string graphs expand linearly on fixed surfaces
Sparse String Graphs and Region Intersection Graphs over Minor-Closed Classes have Linear Expansion
-
Finitely many k-critical graphs in (P4+ℓP1)-free subfamilies
Vertex-critical graphs in subfamilies of $(P_4+\ell P_1)$-free graphs
-
Corrected minima found for reduced Zagreb index of trees
Further results on the lower bound on reduced Zagreb index of trees
-
ReLU networks generate every graph within edit distance d
ReLU Networks for Exact Generation of Similar Graphs
-
Graphs of treewidth k and degree Δ get tree-partitions of width O(kΔ)
Tree-partitions and small-spread tree-decompositions
-
TSP algorithm achieves space-time product 3.7493^N
Improved Space-Time Tradeoffs for Permutation Problems via Extremal Combinatorics
-
Split graph counterexample disproves biclique equality
A counterexample to the conjecture on Biclique Partition number of Split Graphs and related problems
-
Column generation beats compact MILP on real technician routing instances
A column-generation approach for an electricity technician routing and scheduling problem with a lexicographic objective
-
Large bipartite graphs admit equitable colorings with Δ/2 + 1 colors
Equitable coloring of large bipartite graphs
-
Framework yields eight matroid depth measures with six distinct
Measuring Depth of Matroids
-
Reorientation diameter bounded by E/(p/2) plus O(p^2) constant
On the $(\leq p)$-inversion diameter of oriented graphs
-
Vehicle routing encoded with colored permutations needs no extra capacity qubits
Optimal, Qubit-Efficient Quantum Vehicle Routing via Colored-Permutations
-
Geometric count sets lower limit on MDS code repair
Linear Exact Repair in MDS Array Codes: A General Lower Bound and Its Attainability
-
This paper derives explicit forms for the independent domination polynomial of the…
Independent domination polynomial of comaximal graphs of commutative rings
-
3D queens dominate with order n squared pieces
On the Structure of 3D Queen Domination
-
Census dual graphs are nearly planar and triangulated
Census Dual Graphs: Properties and Random Graph Models
-
Zero-divisor graphs of Z_p[x]/(x^c) have explicit spectra
Spectral Properties of Zero-Divisor Graphs of Truncated Polynomial Rings
-
Triplet encoding reproduces Most Permissive Boolean dynamics
A Boolean encoding of the Most Permissive semantics for Boolean networks
-
Treewidth-t graphs admit O(t log t) proper ball compression
Sample compression schemes for balls in structurally sparse graphs
-
Minimal excluded minors for genus g bounded by O(g^{8+ε})
A polynomial bound for the minimal excluded minors for a surface
-
Reappearances lower optimal threshold in secretary problem
Some variations of the secretary problem
-
Exact Matching on bipartite graphs solved in O(n^6) time
Bipartite Exact Matching in P
-
Banach density hits 1/2 only for finite-rank language spaces in 1D
Banach density of generated languages: Dichotomies in topology and dimension
-
Merge-models exactly capture bounded twin-width
On merge-models
-
b-Chromatic number hard on some H-free graphs while tight version is easy
Optimal b-Colourings and Fall Colourings in $H$-Free Graphs
-
Linear reducible configs give near-linear 4-coloring of planar graphs
The Four Color Theorem with Linearly Many Reducible Configurations and Near-Linear Time Coloring
-
Polynomial algorithm solves Geodetic Set on ditrees
Algorithms and Hardness for Geodetic Set on Tree-like Digraphs
-
Product graph proves livelock freedom for all ring sizes
Practical Livelock Analysis in Parameterized Unidirectional Rings
-
k-Irreducible Triangulations Have O(k²g) Triangles
On the size of k-irreducible triangulations
-
Entropy analysis bounds fractional coloring in degenerate graphs
Fractional coloring via entropy
-
Induced acyclic subdigraphs orthogonal to min path partitions
Orthogonality between acyclic subdigraphs and paths in digraphs
-
Nearly polynomial inverse theorem for Gowers U^d at degree d+1
Nearly-polynomial inverse theorem for the U^d norm in degree d+1
-
Random 2-CNF has poly OBDDs outside density interval 0.5-1
The Compilability Thresholds of 2-CNF to OBDD
-
Algorithm lists all Eulerian trails in O(m + z_T) time
Optimal Enumeration of Eulerian Trails in Directed Graphs
-
Induced minor exclusions yield polylog bag bounds in decompositions
Induced Minors and Coarse Tree Decompositions
-
Random k-subsets form matroid bases with prob e^{-c^2/2}
Binomial Random Matroids
-
Maximal outerplanar graphs bound double domination by (n+k)/2
An Upper Bound for the Double Domination Number in Maximal Outerplanar Graphs
-
Capacity bounds derived for hard-core model on triangular lattice
Recoverable systems and the maximal hard-core model on the triangular lattice
-
New conditions rule out more pairs from optimal preorders
Partial Optimality in the Preordering Problem
-
Algebraic conditions decide all finite-domain CSP complexity
Graph Homomorphisms and Universal Algebra
-
Polynomial partitioning yields short labels for semialgebraic graphs
Implicit representations via the polynomial method
-
Sparse coverage functions get poly(t,k,log n) discrepancy
Non-Additive Discrepancy: Coverage Functions in a Beck-Fiala Setting
-
Hybrid algorithm tightens submodular k-matroid bound to 0.819k
Submodular Maximization over a Matroid $k$-Intersection: Multiplicative Improvement over Greedy
-
Almost all vectorial functions have trivial EA-stabilizers
Almost All Vectorial Functions Have Trivial Extended-Affine Stabilizers
-
Chordal graphs have a unique minimal meg-set
An Algorithm for Monitoring Edge-geodetic Sets in Chordal Graphs
-
Bounded TDM-treewidth solves graphic IPs in polynomial time
Totally $\Delta$-Modular Tree Decompositions of Graphic Matrices for Integer Programming