Besonderhede van voorbeeld: 6874983915226187588

Greek

Για παραμετροποιημένα προβλήματα που παραδέχονται ένα πυρήνα που διατηρεί επιπεδότητα και μειώνει το γράφημα εισόδου σε ένα πυρήνα του μεγέθους γραμμικού στην παράμετρο εισόδου, αυτή η προσέγγιση μπορεί να χρησιμοποιηθεί για το σχεδιασμό σταθερών παραμέτρων προσιτών αλγορίθμων το χρόνο λειτουργίας των οποίων εξαρτάται πολυωνυμικά από το μέγεθος του γραφήματος εισόδου και εκθετικά για √k, όπου k είναι η παράμετρος του αλγορίθμου.

Russian

Для параметризованных задач, допускающих параметрическую редукцию, сохраняющую планарность и сокращающую входной файл до ядра с размером, линейно зависящим от параметра, этот подход можно использовать для построения фиксированно-параметрически разрешимых алгоритмов, время выполнения которых зависит полиномиально от размера входного графа и экспоненционально от √k, где k — параметр алгоритма.