Cookies

We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Research & business

Research lectures, seminars and events

The events listed in this area are research seminars, workshops and lectures hosted by Durham University departments and research institutes. If you are not a member of the University, but  wish to enquire about attending one of the events please contact the organiser or host department.


 

Algorithms and Complexity (ACiD) Seminar: On the thinness and proper thinness of a graph

Presented by Flavia Bonomo, Universidad de Buenos Aires
20 October 2020 13:00 in Online

The thinness of a graph is a with parameter introduced by Mannino, Oriolo, Ricci, and Chandran in 2007 as a generalization of interval graphs, which are exactly the 1-thin graphs. When a representation of the graph as a k-thin graph is given, for a constant value k, some NP-complete problems as maximum weighted independent set and bounded coloring with fixed number of colors can be solved in polynomial time. Similarly, the graphs with bounded proper thinness generalize proper interval graphs.

In this talk we will survey the main known results and open problems on thinness and proper thinness. We present the complexity of problems related to the computation of thinness and proper thinness, describe lower and upper bounds, the behavior of the thinness and proper thinness under some graph operations, and relate thinness and proper thinness to other graph invariants in the literature. We will describe also a wide family of problems that can be solved in polynomial time for graphs with bounded thinness, when the k-thin representation of the graph is given. For thinness and proper thinness two, we will present characterizations by means of intersection models and forbidden patterns. We will also relate graphs with thinness at most three to VPG graphs with bounded bend number.

Contact algorithms.complexity@dur.ac.uk for more information