Assigning channels via the meet-in-the-middle approach

DOI10.1007/S00453-015-0004-ZMaRDI QIDQ289931zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Łukasz Kowalik, Arkadiusz Socała

Publication date 31 May 2016

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s00453-015-0004-z

zbMATH Keywords

exponential time hypothesishardness\(T\)-coloringchannel assignmentexponential timemeet-in-the-middle

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Assigning channels via the meet-in-the-middle approach
• Tight lower bound for the channel assignment problem
• Tight lower bound for the channel assignment problem
• An exact algorithm for the channel assignment problem
• Channel assignment via fast zeta transform

Cites work

• An exact algorithm for the channel assignment problem
• An exact algorithm for the generalized list \(T\)-coloring problem
• Channel assignment via fast zeta transform
• Computing Partitions with Applications to the Knapsack Problem
• Counting Paths and Packings in Halves
• Fast exact algorithm for L(2,1)-labeling of graphs
• Graph-Theoretic Concepts in Computer Science
• On the complexity of \(k\)-SAT
• On the span in channel assignment problems: Bounds, computing and counting
• Randomized divide-and-conquer: improved path, matching, and packing algorithms
• Set partitioning via inclusion-exclusion
• The Time Complexity of Constraint Satisfaction
• Tight lower bound for the channel assignment problem

Cited in

(5)

• Channel assignment with large demands
• Tight lower bound for the channel assignment problem
• Channel assignment via fast zeta transform
• Assigning channels via the meet-in-the-middle approach
• Tight lower bound for the channel assignment problem

This page was built for publication: Assigning channels via the meet-in-the-middle approach

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