Assigning channels via the meet-in-the-middle approach
DOI10.1007/s00453-015-0004-zzbMath1339.68119DBLPjournals/algorithmica/KowalikS16OpenAlexW2125759243WikidataQ59472706 ScholiaQ59472706MaRDI QIDQ289931
Ł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
channel assignment\(T\)-coloringhardnessexponential time hypothesisexponential timemeet-in-the-middle
Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)
Cites Work
- Fast exact algorithm for \(L(2,1)\)-labeling of graphs
- 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
- Computing Partitions with Applications to the Knapsack Problem
- Counting Thin Subgraphs via Packings Faster than Meet-in-the-Middle Time
- An Exact Algorithm for the Generalized List $T$-Coloring Problem
- Tight lower bound for the channel assignment problem
- Graph-Theoretic Concepts in Computer Science
- On the complexity of \(k\)-SAT
This page was built for publication: Assigning channels via the meet-in-the-middle approach
