archive
Every paper Pith has read. Search by title, abstract, or pith.
398 papers in cs.DM · page 8
-
Exact minimum wirelength computed for 3-ary cube embeddings
Exact Wirelength of Embedding 3-Ary n-Cubes into certain Cylinders and Trees
-
Nice graphs of degree ≤5 admit distinguishing (Δ+2) edge weightings with local diversity
Neighbour sum distinguishing edge-weightings with local constraints
-
SDP relaxation solves sparse integer least squares exactly under data conditions
An SDP Relaxation for the Sparse Integer Least Squares Problem
-
All graphs on 8 or fewer nodes are 2-interval-PCGs
All Graphs with at most 8 nodes are 2-interval-PCGs
-
Matching partition function limit found for random hypergraphs
Matchings on Random Regular Hypergraphs
-
Stochastic matching reaches 0.382 approximation with patience at least 2
Improved Guarantees for Offline Stochastic Matching via New Ordered Contention Resolution Schemes
-
Elimination distance to degree-d graphs is FPT on planar graphs
Elimination distance to bounded degree on planar graphs
-
New conditions classify which grids are balanceable
On the balanceability of some graph classes
-
2-MU classification reduced to digraph isomorphism
The classification of minimally unsatisfiable 2-CNFs -- a fundamental study
-
Subtour cuts imply matrix-tree SDP bound for TSP
Subtour Elimination Constraints Imply a Matrix-Tree Theorem SDP Constraint for the TSP
-
Vertex cover LP gap equals 2 minus 2 over fractional chromatic number
Integrality Gap of the Vertex Cover Linear Programming Relaxation
-
GAMA solves structured non-convex IPs orders of magnitude faster than Gurobi
GAMA: A Novel Algorithm for Non-Convex Integer Programs
-
All open stable marriage cases with ties resolved
The stable marriage problem with ties and restricted edges
-
Path TSP matches TSP approximability up to any tiny ε
Reducing Path TSP to TSP
-
Canonical augmentation classifies linear codes over small fields
Classification of linear codes using canonical augmentation
-
DFA with n states fits in (σ-1)n log n bits for fast acceptance checks
Succinct Representation for (Non)Deterministic Finite Automata
-
The paper analyzes a combinatorial selection problem where items must be chosen from sets…
Robust Approach to Restricted Items Selection Problem
-
Simplicial instances prove unbounded gaps for TSP SDP relaxations
Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps
-
Classification learning reduces to dualization on poset products
Logical Classification of Partially Ordered Data
-
Domain compression trades shared randomness for fewer samples in distributed tests
Domain Compression and its Application to Randomness-Optimal Distributed Goodness-of-Fit
-
FPT algorithm finds min-reticulation tree-child networks from trees
A Practical Fixed-Parameter Algorithm for Constructing Tree-Child Networks from Multiple Binary Trees
-
ILP finds first n-queens solutions up to size 115
Finding First and Most-Beautiful Queens by Integer Programming
-
Catalan numbers count σ where stack sorting yields non-class sets
Stack sorting with restricted stacks
-
AC^0[⊕] circuits need superpolynomial size for Andreev's Problem
On the $\text{AC}^0[\oplus]$ complexity of Andreev's Problem
-
Three m-eternal domination variants coincide on Christmas cacti
On the m-eternal Domination Number of Cactus Graphs
-
New q-starlike class yields coefficient bounds for multivalent functions
A study of multivalent q-starlike functions connected with circular domain
-
One table lookup adds Jacobi symbol to any left-to-right GCD algorithm
Efficient computation of the Jacobi symbol
-
Conditions allow containing grid fires with online firefighter counts
Online Firefighting on Grids
-
Containment representations characterize graph and poset classes
Containment Graphs, Posets, and Related Classes of Graphs
-
Cographs decide p-forest q-set partitions in polynomial time
Vertex arboricity of cographs
-
Amnesiac flooding terminates in e rounds iff graph is bipartite
On The Termination of a Flooding Process
-
Phase transition in grid navigation solvability at fault rate between 1% and 65%
Navigating an Infinite Space with Unreliable Movements
-
Split domination holds exactly when graph avoids six induced subgraphs
Structural domination and coloring of some ($P_7, C_7$)-free graphs
-
Minimal separators characterize equal connectivities in chordal graphs
Integer Laplacian Eigenvalues of Chordal Graphs
-
Decomposing graphs into almost-disjoint 2-paths is NP-hard
The Almost-Disjoint 2-Path Decomposition Problem
-
Ricci curvature defined for directed hypergraphs
Ollivier Ricci Curvature of Directed Hypergraphs
-
Black-rooted Fibonacci trees introduce new simple properties
About Fibonacci trees. II -- generalized Fibonacci trees
-
Order type realizability drops to expected NP time under noise
Smoothed Analysis of Order Types
-
Exact asymptotics found for approximate Voronoi cell volumes
Approximate Voronoi cells for lattices, revisited
-
Large Steiner triple systems admit block-free sequencings of any fixed length
Block-avoiding point sequencings of arbitrary length in Steiner triple systems
-
Signed graphs extend spectral theory of unsigned graphs
Open problems in the spectral theory of signed graphs
-
Flux graphs measure distance between any two reaction networks
On Quantitative Comparison of Chemical Reaction Network Models
-
NP-hardness shown for 2-connected bottleneck Steiner problem in all p-norm planes
The $2$-connected bottleneck Steiner network problem is NP-hard in any $\ell_p$ plane
-
Energy sum equals Euler characteristic in simplicial complexes
The energy of a simplicial complex
-
Algorithms compute distances and latencies in link streams
On computing distances and latencies in Link Streams
-
Minority processes take Ω(n^{2-ε}) steps to stabilize
Stabilization Time in Minority Processes
-
Chordal graphs get linear recoloring sequences at k >= d+4
Linear transformations between colorings in chordal graphs
-
Matching reconfiguration via cycles is NP-hard on planar graphs
Shortest Reconfiguration of Perfect Matchings via Alternating Cycles
-
Convex cover and partition problems are NP-complete for four graph convexities
Covering graphs with convex sets and partitioning graphs into convex sets
-
Preferred extensions of digraphs enumerated in O*(3^{n/3}) time
Enumeration of Preferred Extensions in Almost Oriented Digraphs