Seminár z teórie grafov - Róbert Lukoťka (28.11.2019)

vo štvrtok 28.11.2019 o 9:50 hod. v miestnosti M/213

---

Prednášajúci: Róbert Lukoťka

Názov: Circular flow number of cubic graphs in O(1.5^n) time

Termín: 28.11.2019, 9:50 hod., M/213

Abstrakt:
We show that the circular flow number of a cubic graph can be determined in time O(1.94^n). The running time can be improved to O(1.5^n) if we do not need to distinguish the circular flow number values between 5 and 6. Finally, we observe that it is possible to decide the flow number of a cubic graph in O(1.26^n) time. We discuss how the results transfer to circular colourings.

 

 

---