Unit and single point interval graphs |
| |
| Authors: | Dieter Rautenbach Jayme L Szwarcfiter |
| |
| Institution: | 1. Institut für Optimierung und Operations Research, Universität Ulm, Ulm, Germany;2. Instituto de Matemática, NCE, and COPPE, Universidade Federal do Rio de Janeiro, Rio de Janeiro, RJ, Brazil |
| |
| Abstract: | We describe a linear time algorithm for the recognition of graphs that have an intersection representation using unit length intervals and single point intervals. Furthermore, we characterize these graphs using forbidden induced subgraphs. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
