Academic Journals Database
Disseminating quality controlled scientific knowledge

Tractabilities and Intractabilities on Geometric Intersection Graphs

Author(s): Ryuhei Uehara

Journal: Algorithms
ISSN 1999-4893

Volume: 6;
Issue: 1;
Start page: 60;
Date: 2013;
Original page

Keywords: bandwidth | chain graphs | graph isomorphism | Hamiltonian path problem | interval graphs | threshold graphs | unit grid intersection graphs

A graph is said to be an intersection graph if there is a set of objects such that each vertex corresponds to an object and two vertices are adjacent if and only if the corresponding objects have a nonempty intersection. There are several natural graph classes that have geometric intersection representations. The geometric representations sometimes help to prove tractability/intractability of problems on graph classes. In this paper, we show some results proved by using geometric representations.
RPA Switzerland

RPA Switzerland

Robotic process automation


Tango Rapperswil
Tango Rapperswil