Maximum Edge Colouring Problem On Graphs That Exclude a Fixed Minor
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F23%3A10473814" target="_blank" >RIV/00216208:11320/23:10473814 - isvavai.cz</a>
Výsledek na webu
<a href="https://doi.org/10.1007/978-3-031-43380-1_21" target="_blank" >https://doi.org/10.1007/978-3-031-43380-1_21</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-031-43380-1_21" target="_blank" >10.1007/978-3-031-43380-1_21</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Maximum Edge Colouring Problem On Graphs That Exclude a Fixed Minor
Popis výsledku v původním jazyce
The maximum edge colouring problem considers the maximum colour assignment to edges of a graph under the condition that every vertex has at most a fixed number of distinct coloured edges incident on it. If that fixed number is q we call the colouring a maximum edge q-colouring. The problem models a non-overlapping frequency channel assignment question on wireless networks. The problem has also been studied from a purely combinatorial perspective in the graph theory literature. We study the question when the input graph is sparse. We show the problem remains NP-hard on 1-apex graphs. We also show that there exists PTAS for the problem on minor-free graphs. The PTAS is based on a recently developed Baker game technique for proper minor-closed classes, thus avoiding the need to use any involved structural results. This further pushes the Baker game technique beyond the problems expressible in the first-order logic.
Název v anglickém jazyce
Maximum Edge Colouring Problem On Graphs That Exclude a Fixed Minor
Popis výsledku anglicky
The maximum edge colouring problem considers the maximum colour assignment to edges of a graph under the condition that every vertex has at most a fixed number of distinct coloured edges incident on it. If that fixed number is q we call the colouring a maximum edge q-colouring. The problem models a non-overlapping frequency channel assignment question on wireless networks. The problem has also been studied from a purely combinatorial perspective in the graph theory literature. We study the question when the input graph is sparse. We show the problem remains NP-hard on 1-apex graphs. We also show that there exists PTAS for the problem on minor-free graphs. The PTAS is based on a recently developed Baker game technique for proper minor-closed classes, thus avoiding the need to use any involved structural results. This further pushes the Baker game technique beyond the problems expressible in the first-order logic.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
—
OECD FORD obor
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Návaznosti výsledku
Projekt
<a href="/cs/project/GA22-17398S" target="_blank" >GA22-17398S: Toky a cykly v grafech na plochách</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Ostatní
Rok uplatnění
2023
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název statě ve sborníku
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISBN
978-3-031-43379-5
ISSN
—
e-ISSN
1611-3349
Počet stran výsledku
14
Strana od-do
291-304
Název nakladatele
Springer
Místo vydání
Switzerland
Místo konání akce
Fribourg, Switzerland
Datum konání akce
28. 6. 2023
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—