Catalogo Articoli (Spogli Riviste)

OPAC HELP

Titolo:
Width-restricted layering of acyclic digraphs with consideration of dummy nodes
Autore:
Branke, J; Leppert, S; Middendorf, M; Eades, P;
Indirizzi:
Univ Karlsruhe, Inst AIFB, D-76128 Karlsruhe, Germany Univ Karlsruhe Karlsruhe Germany D-76128 IFB, D-76128 Karlsruhe, Germany Univ Sydney, Basser Dept Comp Sci, Sydney, NSW 2006, Australia Univ Sydney Sydney NSW Australia 2006 mp Sci, Sydney, NSW 2006, Australia
Titolo Testata:
INFORMATION PROCESSING LETTERS
fascicolo: 2, volume: 81, anno: 2002,
pagine: 59 - 63
SICI:
0020-0190(20020131)81:2<59:WLOADW>2.0.ZU;2-N
Fonte:
ISI
Lingua:
ENG
Keywords:
graph drawing; width-restricted layering; computational complexity;
Tipo documento:
Article
Natura:
Periodico
Settore Disciplinare:
Engineering, Computing & Technology
Citazioni:
5
Recensione:
Indirizzi per estratti:
Indirizzo: Middendorf, M Univ Karlsruhe, Inst AIFB, Kaiserstr 12, D-76128 Karlsruhe, Germany Univ Karlsruhe Kaiserstr 12 Karlsruhe Germany D-76128 rmany
Citazione:
J. Branke et al., "Width-restricted layering of acyclic digraphs with consideration of dummy nodes", INF PROCESS, 81(2), 2002, pp. 59-63

Abstract

This paper deals with the problem of finding graph layerings restricted toa given maximal width. However, other than previous approaches for width-restricted layering, we take into account the space for dummy nodes, which are introduced by edges crossing a layer. The main result is that the problem of finding a width-restricted layering under consideration of dummy nodesis NP-complete even when all regular nodes have the same constant width and all dummy nodes have the same constant width. (C) 2002 Elsevier Science B. V All rights reserved.

ASDD Area Sistemi Dipartimentali e Documentali, Università di Bologna, Catalogo delle riviste ed altri periodici
Documento generato il 26/01/20 alle ore 10:31:43