archive
Every paper Pith has read. Search by title, abstract, or pith.
398 papers in cs.DM · page 6
-
Colorful minors make testing fixed-parameter tractable
Colorful Minors
-
Abelian Cayley graphs contain distinct Hamiltonian cycle classes
Symmetry classes of Hamiltonian cycles
-
Four graph classes split vertices into two locating-dominating sets
Locating-dominating partitions for some classes of graphs
-
Category theory generalizes steady persistence with stability
Stability and Extension of Steady and Ranging Persistence
-
DNFs hit any k solutions with O(sqrt(log k) log log k) terms
CNFs and DNFs with Exactly $k$ Solutions
-
Spanning-tree packing gives optimal conference keys in any quantum network
Spanning-tree-packing protocol for conference key propagation in quantum networks
-
Search yields 49 minimal graphs for LS+ rank 3 and 4107 for rank 4
A Computational Search for Minimal Obstruction Graphs for the Lov\'{a}sz--Schrijver SDP Hierarchy
-
Five crossings per edge allow at most 7(n-2) edges
A first view on the density of 5-planar graphs
-
Randomness recycling nears Shannon entropy bound in online sampling
Efficient Online Random Sampling via Randomness Recycling
-
Edge partitioning reaches sqrt(k) replication factor
Near-optimal edge partitioning via intersecting families
-
16 QAOA layers outperform classical baseline in power grid optimization
End-to-End Speedup for Quantum Simulation-Based Optimization in Power Grid Management
-
Meta-algorithms put families of temporal problems in FPT via interval widths
Families of tractable problems with respect to vertex-interval-membership width and its generalisations
-
Angioedema gene graph subgraphs activate via alternating updates
Robustness of Boolean networks to update modes: an application to hereditary angioedema
-
Deciding minimum firefighters to save a graph is NP-hard
Complexity of Firefighting on Graphs
-
Logic with counting matches hom indistinguishability over pebble forests
Going deep and going wide: Counting logic and homomorphism indistinguishability over graphs of bounded treedepth and treewidth
-
Frequencies in optimal paths flag TSP cycle edges
The frequency $K_i$s for symmetrical traveling salesman problem
-
Tree decomposition found in single-exp time via feedback vertex number
Treewidth Parameterized by Feedback Vertex Number
-
Every finite lattice arises as a stable matching lattice
All finite lattices are stable matching lattices
-
Framework yields constant competitive ratio for grid evacuations
A framework for distributed discrete evacuation strategies
-
Distance-hereditary graphs with distance-hereditary complements get decomposition-based ID
A note on distance-hereditary graphs whose complement is also distance-hereditary
-
Gray graph is a second counterexample to 2-factor conjecture
The Gray graph is pseudo 2-factor isomorphic
-
Constant-distance tree codes with immediacy must vanish in rate
The Rate-Immediacy Barrier in Explicit Tree Code Constructions
-
Pseudo-injective polynomials yield fast solutions to P(X)=B
Solving "pseudo-injective" polynomial equations over finite dynamical systems
-
New sampler hits entropy-optimal coin flips with linearithmic space
Efficient Rejection Sampling in the Entropy-Optimal Range
-
Isometric embedding achieves constant rate 1/8 from Hamming to edit
Constant Rate Isometric Embeddings of Hamming Metric into Edit Metric
-
Interval graphs with three or more vertices are reconstructible
Interval Graphs are Reconstructible
-
Bounded-genus supports exist when subgraphs are cross-free
On Supports for graphs of bounded genus
-
New algorithm counts 29 quadrillion semigroups of genus 76
Exploring the unleaved tree of numerical semigroups up to a given genus
-
Scheduling ratios under uncertainty drop to 2.15 and 2.31
The Power of Amortization on Minimizing Total Completion Time with Explorable Uncertainty
-
FHE performs addition and multiplication on encrypted numbers
The Beginner's Textbook for Fully Homomorphic Encryption
-
Conditions on substitutions make numeration systems positional
Positionality of Dumont--Thomas numeration systems for integers
-
RL supports diameter n(n-1)/2 conjecture for S_n Cayley graph
CayleyPy RL: Pathfinding and Reinforcement Learning on Cayley Graphs
-
Word-representable graphs require Ω(log n) comparability covers
Word-representability and comparability: Minimal forbidden induced subgraphs and cover number bounds
-
Classical solver beats AI methods on maximum independent set
Unrealized Expectations: Comparing AI Methods vs Classical Algorithms for Maximum Independent Set
-
Coefficients characterize injective polynomials over finite sets
Injectivity of polynomials over finite discrete dynamical systems
-
O(log n) approximation for (p,q) flexible graph connectivity
An O(log n)-Approximation Algorithm for (p,q)-Flexible Graph Connectivity via Independent Rounding
-
Approximate hypergraph colouring is NP-hard except one case
Complexity of approximate conflict-free, linearly-ordered, and nonmonochromatic hypergraph colourings
-
Independent Set stays hard under n^{1/2-o(1)} edits
Answering Related Questions
-
Smallest graph with rank ℓ needs exactly 3ℓ vertices
Stable Set Polytopes with Rank $|V(G)|/3$ for the Lov\'{a}sz--Schrijver SDP Operator
-
Hamiltonian dynamics force connectivity in Boolean network graphs
Hamiltonian dynamics of Boolean networks
-
Quantum heuristics act as subroutines in exact vehicle routing solvers
Quantum Subroutines in Branch-Price-and-Cut for Vehicle Routing
-
Either k distant cycles or small X leaves forest after radius deletion
Erd\H{o}s--P\'{o}sa property of cycles that are far apart
-
Branch-and-bound speeds flight planning tenfold under real restrictions
Logic-Constrained Shortest Paths for Flight Planning
-
CMSO-transductions output modular
CMSO-transducing tree-like graph decompositions
-
Algorithm lists all cycle permutation graphs to 34 vertices
Generation of Cycle Permutation Graphs and Permutation Snarks
-
L1 vector of size (m+n)/2 avoids m hyperplanes
Hyperplanes Avoiding Problem and Integer Points Counting in Polyhedra
-
Redundancy suffices for CSP sparsification
Redundancy Is All You Need (for CSP Sparsification)
-
Pathwidth plus one bounds fractional list packing
Fractional list packing for layered graphs
-
Hereditary bisection yields Omega(hb/Delta) bound on tree congestion
Approximation of Spanning Tree Congestion using Hereditary Bisection
-
Hofstadter-like functions ordered by recursion nesting
Pointwise order of generalized Hofstadter functions G, H and beyond