Cover Image

Directed Hypercube Routing, a Generalized Lehman-Ron Theorem, and Monotonicity Testing

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chakrabarty, Deeparnab, Seshadhri, C.
Format:	Preprint
Published:	2024
Subjects:	Discrete Mathematics Data Structures and Algorithms Combinatorics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning
by: Chakrabarty, Deeparnab, et al.
Published: (2025)

A Dichotomy Theorem for Linear Time Homomorphism Orbit Counting in Bounded Degeneracy Graphs
by: Paul-Pena, Daniel, et al.
Published: (2022)

Sandwich Monotonicity and the Recognition of Weighted Graph Classes
by: Beisegel, Jesse, et al.
Published: (2025)

Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness
by: Zhang, Bohang, et al.
Published: (2024)

Improved bounds for the zeros of the chromatic polynomial via Whitney's Broken Circuit Theorem
by: Jenssen, Matthew, et al.
Published: (2023)

Subgraph Counting in Subquadratic Time for Bounded Degeneracy Graphs
by: Paul-Pena, Daniel, et al.
Published: (2024)

Near-linear time subhypergraph counting in bounded degeneracy hypergraphs
by: Paul-Pena, Daniel, et al.
Published: (2025)

Isomorphism Testing Parameterized by Genus and Beyond
by: Neuen, Daniel
Published: (2021)

Exact and Heuristic Computation of the Scanwidth of Directed Acyclic Graphs
by: Holtgrefe, Niels, et al.
Published: (2024)

Paths and Intersections: Characterization of Quasi-metrics in Directed Okamura-Seymour Instances
by: Chen, Yu, et al.
Published: (2024)

Isomorphism Testing for Graphs Excluding Small Topological Subgraphs
by: Neuen, Daniel
Published: (2020)

A $d^{1/2+o(1)}$ Monotonicity Tester for Boolean Functions on $d$-Dimensional Hypergrids
by: Black, Hadley, et al.
Published: (2023)

Generating minimal redundant and maximal irredundant sets in incidence graphs
by: Castelo, Emanuel, et al.
Published: (2026)

Circulant TSP: Vertices of the Edge-Length Polytope and Superpolynomial Lower Bounds
by: Gutekunst, Samuel C.
Published: (2025)

Generalising the maximum independent set algorithm via Boolean networks
by: Gadouleau, Maximilien, et al.
Published: (2024)

Enumerating minimal dominating sets and variants in chordal bipartite graphs
by: Castelo, Emanuel, et al.
Published: (2025)

On the complexity of finding a spanning even tree in a graph
by: Hanaka, Tesshu, et al.
Published: (2024)

A note on approximating the average degree of bounded arboricity graphs
by: Eden, Talya, et al.
Published: (2026)

On the number of $k$-mers admitting a given lexicographical minimizer
by: Ingels, Florian, et al.
Published: (2024)

Lettericity of graphs: an FPT algorithm and a bound on the size of obstructions
by: Alecu, Bogdan, et al.
Published: (2024)

Matrix Scaling: a New Heuristic for the Feedback Vertex Set Problem
by: Shook, James M., et al.
Published: (2025)

Constructive Characterization and Recognition Algorithm for Grafts with a Connected Minimum Join
by: Kita, Nanano
Published: (2025)

Non-Additive Discrepancy: Coverage Functions in a Beck-Fiala Setting
by: Avila, Tatiana Rocha, et al.
Published: (2026)

A Quadratic Vertex Kernel and a Subexponential Algorithm for Subset-FAST
by: Jana, Satyabrata, et al.
Published: (2025)

Towards the Characterization of Terminal Cut Functions: a Condition for Laminar Families
by: Chen, Yu, et al.
Published: (2023)

Bounded indegree $k$-forests problem and a faster algorithm for directed graph augmentation
by: Arkhipov, Pavel, et al.
Published: (2024)

On the time complexity of finding a well-spread perfect matching in bridgeless cubic graphs
by: Ghanbari, Babak, et al.
Published: (2025)

An efficient algorithm for $\mathcal{F}$-subgraph-free Edge Deletion on graphs having a product structure
by: An, Shinwoo, et al.
Published: (2025)

A Near-Linear-Time Algorithm for Finding a Well-Spread Perfect Matching in Bridgeless Cubic Graphs
by: Ghanbari, Babak, et al.
Published: (2026)

Deterministic approximate counting of colorings with fewer than $2Δ$ colors via absence of zeros
by: Bencs, Ferenc, et al.
Published: (2024)

Approximating maximum-size properly colored forests
by: Bai, Yuhang, et al.
Published: (2024)

Problems on Group-labeled Matroid Bases
by: Hörsch, Florian, et al.
Published: (2024)

$α_i$-Metric Graphs: Hyperbolicity
by: Dragan, Feodor F., et al.
Published: (2024)

Rainbow Arborescence Conjecture
by: Bérczi, Kristóf, et al.
Published: (2024)

Cuts in Graphs with Matroid Constraints
by: Banik, Aritra, et al.
Published: (2024)

Robust Contraction Decomposition for Minor-Free Graphs and its Applications
by: Bandyapadhyay, Sayan, et al.
Published: (2024)

Randomized Greedy Online Edge Coloring Succeeds for Dense and Randomly-Ordered Graphs
by: Dudeja, Aditi, et al.
Published: (2024)

Deterministic approximation for the volume of the truncated fractional matching polytope
by: Guo, Heng, et al.
Published: (2024)

Clique-free t-matchings in degree-bounded graphs
by: Paluch, Katarzyna, et al.
Published: (2024)

A logarithmic approximation of linearly ordered colourings
by: Håstad, Johan, et al.
Published: (2024)