Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs
We prove essentially tight lower bounds, conditionally to the Exponential Time Hypothesis, for two fundamental but seemingly very different cutting problems on surface-embedded graphs: the Shortest Cut Graph problem and the Multiway Cut problem. A cut graph of a graph $G$ embedded on a surface $S$ i...
Gorde:
| Egile Nagusiak: | , , , |
|---|---|
| Formatua: | Artikulua |
| Argitaratua: |
2019
|
| Gaiak: | |
| Sarrera elektronikoa: | https://arxiv.org/abs/1903.08603 http://arxiv.org/abs/1903.08603 |
| Etiketak: |
Etiketarik gabe, Izan zaitez lehena erregistro honi etiketa jartzen!
|