45 papers
This paper demonstrates that a simple exact method can solve nearly all classical benchmark instances of the Traveling Salesman Problem with Time Windows in under ten seconds, revealing that these datasets are no longer representative for evaluating algorithmic performance or training machine learning models due to their exploitable structure.
This paper proves that asymptotically almost all vectorial functions over finite fields possess trivial extended-affine stabilizers, implying that the number of equivalence classes matches the naive estimate and that random sampling is a highly effective strategy for cryptographic primitive design due to the exponential rarity of functions with nontrivial stabilizers.
This paper proves the long-standing Erdős Matching Conjecture, establishing that the maximum size of a family of -sized subsets of containing no pairwise disjoint sets is bounded by the larger of two canonical extremal constructions.
This paper provides an accessible, modernized proof of Ralph Seifert's 1971 result that no prime functional digraphs exist, thereby resolving a recent conjecture by Antonio E. Porreca.
This paper investigates a novel notion of polytope rigidity where edge lengths and face planarity are preserved while face shapes may vary, proving that convex polytopes are generically rigid in dimension three and conjecturing this holds for all dimensions .
This paper identifies three necessary conditions for the existence of acyclic T-odd orientations, defines and characterizes polynomial graph classes where these conditions are sufficient, and provides constructive polynomial-time algorithms to build such orientations for these classes and their Cartesian products.
This paper investigates the spectral properties of degree-based weighted adjacency matrices for complete and crown multipartite graphs, characterizes families with three distinct eigenvalues and integral spectra, corrects previous findings on energy changes after edge deletion, and resolves an open problem regarding ISI energy in multipartite graphs.
This paper investigates Max-Cut instances on complete graphs with geometrically decreasing edge weights, establishing a sharp phase diagram for the optimality of isolated cuts based on threshold polynomials and conjecturing their global optimality for sufficiently large .
This paper investigates the domination polynomial of the co-maximal graph by deriving explicit formulas for specific cases of , establishing structural connections for general , and analyzing the unimodality, log-concavity, and modulus bounds of its roots.
This paper systematically determines the circular chromatic indices of small graphs and multigraphs with maximum degrees up to 6, constructs infinite families of graphs with specific fractional indices, and refutes edge-connectivity variants of the "Upper Gap Conjecture."
This paper proposes a column-generation-based algorithmic framework to efficiently solve both splittable and unsplittable variants of the capacitated Multi-Commodity Flow problem with convex, potentially non-differentiable, link cost functions, offering a robust optimization approach for managing traffic in telecommunication networks.
This paper introduces HYGENE, the first deep learning-based diffusion method that generates realistic and diverse hypergraphs by iteratively expanding a bipartite representation from a single connected node pair through a progressive local expansion process.
This paper presents a simplified and fully analyzed sublinear-time algorithm that achieves a -approximation of the average degree in bounded arboricity graphs using queries, thereby recovering logarithmic factors lost in previous work and offering a modified version with query complexity.
This paper introduces permutation match puzzles on grids, characterizing their solvability via an acyclic constraint graph condition, providing a hook length formula for counting solutions, offering an algorithm for minimal repairs in the basic case, and proving that generalizing the problem to arbitrary permutations renders minimal repair NP-complete.
This paper establishes that the size difference between optimal Boolean circuits and formulas over the AIG basis is strictly limited to 0 or 1, characterizing the precise conditions under which sharing occurs and proving that any non-zero gap arises exclusively from a single gate with fan-out 2.
This paper investigates the state complexity of automata recognizing relations and operations on -automatic sequences, establishing a link between the subword complexity of interior sequences and the state complexity of their linear subsequences while resolving a recent question by Zantema and Bosma regarding most-significant-digit-first inputs.
This paper provides a complete proof for the previously proposed upper bound of on the double domination number of maximal outerplanar graphs, correcting an earlier incomplete proof by Abd Aziz, Rad, and Kamarulhaili.
This paper establishes that for a set of phylogenetic trees with leaves, if is sufficiently small (specifically ), the trees can be constructed to have virtually no common structure, thereby forcing any network displaying them to require nearly the maximum possible number of reticulations, .
This paper employs the localization framework to improve existing upper bounds on the number of cliques in graphs with bounded maximum degree or path length, while also providing structural characterizations of the extremal graphs that attain these sharper bounds.
This paper initiates a comprehensive study of -free graph drawings by establishing tight upper and lower bounds on edge density for every combination of drawing style, graph type, and forbidden cell type, while also characterizing simple graphs that admit drawings avoiding specific cell types and improving existing bounds for quasiplanar drawings.