| Revista: | Pesquisa operacional |
| Base de datos: | PERIÓDICA |
| Número de sistema: | 000313102 |
| ISSN: | 0101-7438 |
| Autores: | Guedes, André Luiz Pires1 Markenzon, Lilian2 |
| Instituciones: | 1Universidade Federal do Parana, Departamento de Informatica, Curitiba, Parana. Brasil 2Universidade Federal do Rio de Janeiro, Nucleo de Computacao Eletronica, Rio de Janeiro. Brasil |
| Año: | 2005 |
| Periodo: | Sep-Dic |
| Volumen: | 25 |
| Número: | 3 |
| Paginación: | 383-390 |
| País: | Brasil |
| Idioma: | Inglés |
| Tipo de documento: | Artículo |
| Enfoque: | Descriptivo |
| Resumen en inglés | Directed hypergraphs are generalizations of digraphs and can be used to model binary relations among subsets of a given set. Planarity of hypergraphs was studied by Johnson and Pollak; in this paper we extend the planarity concept to directed hypergraphs. It is known that the planarity of a digraph relies on the planarity of its underlying graph. However, for directed hypergraphs, this property do not apply and we propose a new approach which generalizes the usual concept. We also show that the complexity of the recognition of a directed hypergraph as planar is linear on the size of the hypergraph |
| Resumen en portugués | Hipergrafos direcionados são generalizações de digrafos, e são utilizados na modelagem de relações binárias entre subconjuntos de um dado conjunto. O problema da planaridade em hipergrafos foi estudado por Johnson e Pollak; neste trabalho estendemos o conceito de planaridade para hipergrafos direcionados. É noção conhecida que a planaridade de hipergrafos depende da planaridade de seu grafo subjacente. Entretanto, para hipergrafos direcionados, esta propriedade não pode ser aplicada e propomos uma nova abordagem que generaliza o conceito tradicional. Mostramos também que a complexidade de testar a planaridade de um hipergrafo direcionado é linear no tamanho do hipergrafo |
| Disciplinas: | Matemáticas |
| Palabras clave: | Matemáticas aplicadas, Hipergrafos dirigidos, Planaridad, Algoritmos |
| Keyword: | Mathematics, Applied mathematics, Directed hypergraphs, Planarity, Algorithms |
| Texto completo: | Texto completo (Ver HTML) |
