Channel allocation revisited through 1-extendability of graphs

DOI10.1016/J.TCS.2025.115436MaRDI QIDQ6930235zbMATH OpenFDO

Authors Anthony Busson, Malory Marin, Rémi Watrigant

Publication date 16 September 2025

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2025.115436

zbMATH Keywords

1-extendabilitychannel allocationgraph coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Network protocols (68M12) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Cites work

• 1-extendability of independent sets
• A polynomial-time algorithm for solving the hidden subset sum problem
• A survey of the algorithmic aspects of modular decomposition
• Beyond recognizing well-covered graphs
• Computing well-covered vector spaces of graphs using modular decomposition
• Modular decomposition and transitive orientation
• More about subcolorings
• Nonnegative integral subset representations of integer sets
• Parameterized algorithms
• Recognizing well covered graphs of families with special \(P _{4}\)-components
• Some Common Properties for Regularizable Graphs, Edge-Critical Graphs and B-Graphs
• Some covering concepts in graphs
• Speeding up discrete log and factoring based schemes via precomputations
• The hardness of the hidden subset sum problem and its cryptographic implications
• Well-covered graphs and extendability

This page was built for publication: Channel allocation revisited through 1-extendability of graphs

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