Kernelization of compressing two-dimensional routing tables with order

DOI10.1016/J.DAM.2026.05.008MaRDI QIDQ7289247zbMATH OpenFDO

Authors F. Giroire, Frédéric Havet, Joanna Moulierac

Publication date 2 July 2026

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DAM.2026.05.008

Mathematics Subject Classification ID

Graph theory (05Cxx) Computer science (68-XX) Theory of computing (68Qxx)

Cites work

• \(\text{Kernel}(s)\) for problems with no kernel: on out-trees with many leaves
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Compressing rectilinear pictures and minimizing access control lists
• Compressing two-dimensional routing tables
• Cross-composition: a new technique for kernelization lower bounds
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• scientific article; zbMATH DE number 7053262 (Why is no real title available?)
• Infeasibility of instance compression and succinct PCPs for NP
• Kernel bounds for disjoint cycles and disjoint paths
• Kernelization Lower Bounds by Cross-Composition
• Kernelization lower bounds through colors and IDs
• Lower bounds for kernelization
• On problems without polynomial kernels
• On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
• On the complexity of compressing two dimensional routing tables with order
• Parametrized complexity theory.
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• Two edge modification problems without polynomial kernels

This page was built for publication: Kernelization of compressing two-dimensional routing tables with order

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7289247)