Assigning channels via the meet-in-the-middle approach
DOI10.1007/S00453-015-0004-ZzbMATH Open1339.68119DBLPjournals/algorithmica/KowalikS16OpenAlexW2125759243WikidataQ59472706 ScholiaQ59472706MaRDI QIDQ289931FDOQ289931
Authors: Łukasz Kowalik, Arkadiusz Socała 
Publication date: 31 May 2016
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-015-0004-z
Recommendations
exponential time hypothesishardness\(T\)-coloringchannel assignmentexponential timemeet-in-the-middle
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)
Cites Work
- On the complexity of \(k\)-SAT
- An exact algorithm for the channel assignment problem
- On the span in channel assignment problems: Bounds, computing and counting
- Channel assignment via fast zeta transform
- The Time Complexity of Constraint Satisfaction
- Set partitioning via inclusion-exclusion
- Counting Paths and Packings in Halves
- Randomized divide-and-conquer: improved path, matching, and packing algorithms
- Fast exact algorithm for \(L(2,1)\)-labeling of graphs
- Computing Partitions with Applications to the Knapsack Problem
- An exact algorithm for the generalized list \(T\)-coloring problem
- Tight lower bound for the channel assignment problem
- Graph-Theoretic Concepts in Computer Science
Cited In (5)
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)
