Projekte pro Jahr
Abstract
We provide various combinatorial characterizations of universally linearizable graphs that are centered around the structure of source-to-sink paths and around certain forbidden subgraphs. Our characterizations lead to fast and simple recognition algorithms for universally linearizable graphs. Furthermore, we establish the intractability of deciding whether a concrete instance of the QSPP (with a given graph and given arc interaction costs) is linearizable.
Originalsprache | englisch |
---|---|
Titel | Graph-Theoretic Concepts in Computer Science |
Untertitel | WG 2021 |
Redakteure/-innen | Łukasz Kowalik, Michał Pilipczuk, Pawel Rzążewski |
Herausgeber (Verlag) | Springer |
Seiten | 245-256 |
Seitenumfang | 12 |
ISBN (Print) | 9783030868376 |
DOIs | |
Publikationsstatus | Veröffentlicht - 20 Sept. 2021 |
Veranstaltung | 47th International Workshop on Graph-Theoretic Concepts in Computer Science: WG 2021 - Warsaw, Polen Dauer: 23 Juni 2021 → 25 Juni 2021 |
Publikationsreihe
Name | Springer Lecture Notes in Computer Science |
---|---|
Herausgeber (Verlag) | Springer |
Band | 12911 |
Konferenz
Konferenz | 47th International Workshop on Graph-Theoretic Concepts in Computer Science |
---|---|
Kurztitel | WG 2021 |
Land/Gebiet | Polen |
Ort | Warsaw |
Zeitraum | 23/06/21 → 25/06/21 |
ASJC Scopus subject areas
- Allgemeine Mathematik
Fields of Expertise
- Information, Communication & Computing
Treatment code (Nähere Zuordnung)
- Basic - Fundamental (Grundlagenforschung)
Fingerprint
Untersuchen Sie die Forschungsthemen von „Linearizable Special Cases of the Quadratic Shortest Path Problem“. Zusammen bilden sie einen einzigartigen Fingerprint.Projekte
- 1 Abgeschlossen
-
DK: Diskrete Mathematik
Ebner, O. (Teilnehmer (Co-Investigator)), Lehner, F. (Teilnehmer (Co-Investigator)), Greinecker, F. (Teilnehmer (Co-Investigator)), Burkard, R. (Teilnehmer (Co-Investigator)), Wallner, J. (Projektleiter (Principal Investigator)), Elsholtz, C. (Teilnehmer (Co-Investigator)), Woess, W. (Teilnehmer (Co-Investigator)), Raseta, M. (Teilnehmer (Co-Investigator)), Bazarova, A. (Teilnehmer (Co-Investigator)), Krenn, D. (Teilnehmer (Co-Investigator)), Lehner, F. (Teilnehmer (Co-Investigator)), Kang, M. (Teilnehmer (Co-Investigator)), Tichy, R. (Projektleiter (Principal Investigator)), Sava-Huss, E. (Teilnehmer (Co-Investigator)), Klinz, B. (Projektleiter (Principal Investigator)), Heuberger, C. (Projektleiter (Principal Investigator)), Grabner, P. (Projektleiter (Principal Investigator)), Barroero, F. (Teilnehmer (Co-Investigator)), Cuno, J. (Teilnehmer (Co-Investigator)), Kreso, D. (Teilnehmer (Co-Investigator)), Berkes, I. (Projektleiter (Principal Investigator)) & Kerber, M. (Teilnehmer (Co-Investigator))
1/05/10 → 30/06/24
Projekt: Forschungsprojekt