9-13 June 2013
Koper, Slovenia
UTC timezone
Home > Timetable > Contribution details
PDF | XML

When FO properties are efficiently solvable on interval graphs

Presented by Dr. Petr HLINěNý
Type: Oral presentation
Track: Discrete and Computational Geometry

Content

FO (first-order logic) properties include, for instance, the dominating set and subgraph isomorphism problems. We investigate the question, on which subclasses of interval graphs these problems have efficient (parameterized) algorithms--while this is the case of unit interval graphs, no such general algorithmic metatheorem is possible on all interval graphs. We prove that fixed-parameter tractability of FO holds on interval representations using any finite set of interval lengths, but cannot be true when any infinite dense set of lengths is allowed.

Place

Location: Koper, Slovenia

Primary authors

More

Co-authors

More