A Constructive linear time algorithm for small cutwidth
Visualitza/Obre
Estadístiques de LA Referencia / Recolecta
Inclou dades d'ús des de 2022
Cita com:
hdl:2117/96453
Tipus de documentReport de recerca
Data publicació2000-09
Condicions d'accésAccés obert
Tots els drets reservats. Aquesta obra està protegida pels drets de propietat intel·lectual i
industrial corresponents. Sense perjudici de les exempcions legals existents, queda prohibida la seva
reproducció, distribució, comunicació pública o transformació sense l'autorització del titular dels drets
Abstract
The cutwidth of a graph G is defined to be the smallest integer k such that the vertices of G can be arranged in a linear layout
[v(1),...,v(n)] in such a way that for every i=1,...,n-1, there are at most k edges with the one endpoint in {v(1),...,v(i)} and the
other in {v(i+1),...,v(n)}. In this paper we show how to construct, for any constant k, a linear time algorithm that for any input
graph G, answers whether G has cutwidth at most k and, in the case of a positive answer, outputs the corresponding linear
layout.
CitacióThilikos, D., Serna, M., Bodlaender, H. "A Constructive linear time algorithm for small cutwidth". 2000.
Forma partLSI-00-48-R
Col·leccions
Fitxers | Descripció | Mida | Format | Visualitza |
---|---|---|---|---|
R00-48.ps | 310,6Kb | Postscript | Visualitza/Obre |