Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • Treffer 2 von 19
Zurück zur Trefferliste

Efficient Enumeration of Acyclic Graph Orientations with Sources or Sinks Revisited

Zitieren Sie bitte immer diese URN: urn:nbn:de:0297-zib-77684
  • In a recent paper, Conte et al. [CGMR2017] presented an algorithm for enumerating all acyclic orientations of a graph G=(V,E) with a single source (and related orientations) with delay O(|V||E|). In this paper we revisit the problem by going back to an early paper by de Fraysseix et al. [FMR1995], who proposed an algorithm for enumerating all bipolar orientations of a graph based on a recursion formula. We first formalize de Fraysseix et al.'s algorithm for bipolar orientations and determine that its delay is also O(|V||E|). We then apply their recursion formula to the case of Conte et al.'s enumeration problem and show that this yields a more efficient enumeration algorithm with delay O(\sqrt(|V|)|E|). Finally, a way to further streamline the algorithm that leads to a particularly simple implementation is suggested.

Volltext Dateien herunterladen

Metadaten exportieren

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar Statistik - Anzahl der Zugriffe auf das Dokument
Metadaten
Verfasserangaben:Kai-Helge Becker, Benjamin HillerORCiD
Dokumentart:ZIB-Report
Freies Schlagwort / Tag:acyclic orientations; bipolar orientations; enumeration algorithm; multiple sources and sinks
MSC-Klassifikation:05-XX COMBINATORICS (For finite fields, see 11Txx)
68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
CCS-Klassifikation:J. Computer Applications
Datum der Erstveröffentlichung:01.03.2020
Schriftenreihe (Bandnummer):ZIB-Report (20-05)
ISSN:1438-0064
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.