Pubblicazioni

Autori:

Cáceres, Manuel; Cairo, Massimo; Mumey, Brendan; Rizzi, Romeo; Tomescu, Alexandru I.

Titolo:

A Linear-Time Parameterized Algorithm for Computing the Width of a DAG

Anno:

2021

Tipologia prodotto:

Contributo in atti di convegno

Tipologia ANVUR:

Contributo in Atti di convegno

Lingua:

Inglese

Nome rivista:

LECTURE NOTES IN COMPUTER SCIENCE

ISSN Rivista:

0302-9743

N° Volume:

12911

Titolo del Convegno:

International Workshop on Graph-Theoretic Concepts in Computer Science

Luogo:

Virtual, Online

Periodo:

23 June 2021 through 25 June 2021

Editore:

Springer Verlag Germany

Casa editrice:

Springer Verlag Germany

ISBN:

978-3-030-86837-6

Intervallo pagine:

257-269

Parole chiave:

Directed acyclic graph Maximum antichain DAG width Posets Parameterized algorithms Reachability queries

Breve descrizione dei contenuti:

The width k of a directed acyclic graph (DAG) =(,) equals the largest number of pairwise non-reachable vertices. Computing the width dates back to Dilworth’s and Fulkerson’s results in the 1950s, and is doable in quadratic time in the worst case. Since k can be small in practical applications, research has also studied algorithms whose complexity is parameterized on k. Despite these efforts, it is still open whether there exists a linear-time (()(||+||)) parameterized algorithm computing the width . We answer this question affirmatively by presenting an (24||+2||) time algorithm, based on a new notion of frontier antichains. As we process the vertices in a topological order, all frontier antichains can be maintained with the help of several combinatorial properties, paying only f(k) along the way. The fact that the width can be computed by a single f(k)-sweep of the DAG is a new surprising insight into this classical problem. Our algorithm also allows deciding whether the DAG has width at most w in time ((min(,))(||+||)).

Id prodotto:

124798

Handle IRIS:

11562/1057342

ultima modifica:

11 novembre 2022

Citazione bibliografica:

Cáceres, Manuel; Cairo, Massimo; Mumey, Brendan; Rizzi, Romeo; Tomescu, Alexandru I., A Linear-Time Parameterized Algorithm for Computing the Width of a DAG in «LECTURE NOTES IN COMPUTER SCIENCE» vol. 12911 Springer Verlag Germany  in WG 2021: Graph-Theoretic Concepts in Computer Science , Springer Verlag Germany , Atti di "International Workshop on Graph-Theoretic Concepts in Computer Science" , Virtual, Online , 23 June 2021 through 25 June 2021 , 2021 , pp. 257-269

Consulta la scheda completa presente nel repository istituzionale della Ricerca di Ateneo