Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

07.11.2019 | Ausgabe 1/2020

Journal of Combinatorial Optimization 1/2020

Efficient algorithms for measuring the funnel-likeness of DAGs

Zeitschrift:
Journal of Combinatorial Optimization > Ausgabe 1/2020
Autoren:
Marcelo Garlet Millani, Hendrik Molter, Rolf Niedermeier, Manuel Sorge
Wichtige Hinweise
MGM was partially supported by the DFG, Project FPTinP (NI 369/16). HM was partially supported by the DFG, Project MATE (NI 369/17). MS was partially supported by the People Programme (Marie Curie Actions) of the European Union’s Seventh Framework Programme (FP7/2007-2013) under REA Grant Agreement Number 631163.11, by the Israel Science Foundation (Grant No. 551145/14), and by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme under Grant Agreement Number 714704.
An extended abstract of this work appeared in the proceedings of the 5th International Symposium on Combinatorial Optimization (ISCO ’18) (Millani et al. 2018). This version contains all proof details, additional inapproximability results, and extended experimental findings. Work started while all authors were with TU Berlin. The main work of MS was carried out while with Ben-Gurion University of the Negev, Beer Sheva, Israel.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Abstract

We propose funnels as a new natural subclass of DAGs. Intuitively, a DAG is a funnel if every source-sink path can be uniquely identified by one of its arcs. Funnels are an analogue to trees for directed graphs, being more restrictive than DAGs but more expressive than mere in-/out-trees. Computational problems such as finding vertex-disjoint paths or tracking the origin of memes remain NP-hard on DAGs while on funnels they become solvable in polynomial time. Our main focus is the algorithmic complexity of finding out how funnel-like a given DAG is. To this end, we identify the NP-hard problem of computing the arc-deletion distance of a given DAG to a funnel. We develop efficient exact and approximation algorithms for the problem and test them on synthetic random graphs and real-world graphs.

Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 50.000 Bücher
  • über 380 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Maschinenbau + Werkstoffe




Testen Sie jetzt 30 Tage kostenlos.

Literatur
Über diesen Artikel

Weitere Artikel der Ausgabe 1/2020

Journal of Combinatorial Optimization 1/2020 Zur Ausgabe

Premium Partner

    Bildnachweise