On counting interval lengths of interval graphs |
| |
| Authors: | Má rcia R. Cerioli,Fabiano de S. Oliveira,Jayme L. Szwarcfiter |
| |
| Affiliation: | a COPPE/Engenharia de Sistemas e Computação, Universidade Federal do Rio de Janeiro, Caixa Postal 68511, 21941-972, Rio de Janeiro, Brazilb Instituto de Matemática, Universidade Federal do Rio de Janeiro, Caixa Postal 68530, 21941-909, Rio de Janeiro, Brazilc Núcleo de Computação Eletrônica, Universidade Federal do Rio de Janeiro, Caixa Postal 2324, 20010-974, Rio de Janeiro, Brazil |
| |
| Abstract: | Given an interval graph G, the interval count problem is that of computing the minimum number IC(G) of interval lengths needed to represent G. Although the problem of deciding whether IC(G)=1 is equivalent to that of recognizing unit-interval graphs, which is a well-known problem having several efficient recognition approaches, very little is known about deciding efficiently whether IC(G)=k for fixed k≥2. We provide efficient computations of the interval count of generalizations of threshold graphs. |
| |
| Keywords: | Interval graphs Interval count Lengths of intervals |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
