A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs | Zendy

Mark de Berg | Zendy; Hans L. Bodlaender | Zendy; Sándor Kisfaludi-Bak | Zendy; Dániel Marx | Zendy; Tom C. van der Zanden | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs

Author(s) -

Mark de Berg,

Hans L. Bodlaender,

Sándor Kisfaludi-Bak,

Dániel Marx,

Tom C. van der Zanden

Publication year - 2020

Publication title -

siam journal on computing

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.533

H-Index - 122

eISSN - 1095-7111

pISSN - 0097-5397

DOI - 10.1137/20m1320870

Subject(s) - exponential time hypothesis , treewidth , combinatorics , mathematics , discrete mathematics , upper and lower bounds , chordal graph , maximal independent set , dominating set , intersection (aeronautics) , independent set , embedding , time complexity , exponential function , approximation algorithm , intersection graph , pathwidth , algorithm , graph , computer science , line graph , 1 planar graph , vertex (graph theory) , mathematical analysis , artificial intelligence , engineering , aerospace engineering

We give an algorithmic and lower bound framework that facilitates the construction of subexponential algorithms and matching conditional complexity bounds. It can be applied to intersection graphs ...

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research