Graph theory is used to investigate three different problems arising in air traffic management. First, using a polynomial reduction from a graph partitioning problem, it is shown that both the airspace sectorization problem and its incremental counterpart, the sector combination problem are NP-hard, in general, under several simple workload models. Second, using a polynomial time reduction from maximum independent set in graphs, it is shown that for any fixed e, the problem of finding a solution to the minimum delay scheduling problem in traffic flow management that is guaranteed to be within n1-e of the optimal, where n is the number of aircraft in the problem instance, is NP-hard. Finally, a problem arising in precision arrival scheduling is formulated and solved using graph reachability. These results demonstrate that graph theory provides a powerful framework for modeling, reasoning about, and devising algorithmic solutions to diverse problems arising in air traffic management.


    Zugriff

    Zugriff über TIB

    Verfügbarkeit in meiner Bibliothek prüfen


    Exportieren, teilen und zitieren



    Titel :

    Applying Graph Theory to Problems in Air Traffic Management


    Beteiligte:

    Kongress:

    AIAA Aviation and Aeronautics Forum ; 2017 ; Denver, CO, United States


    Erscheinungsdatum :

    05.06.2017


    Medientyp :

    Sonstige


    Format :

    Keine Angabe


    Sprache :

    Englisch




    Applying Graph Theory to Problems in Air Traffic Management

    Farrahi, Amir H. / Goldberg, Alan T. / Bagasol, Leonard et al. | AIAA | 2017


    Applying Graph Theory to Problems in Air Traffic Management (AIAA 2017-3775)

    Farrahi, Amir H. / Goldberg, Alan T. / Bagasol, Leonard et al. | British Library Conference Proceedings | 2017


    Traffic management system applying deep neural network to intelligent traffic

    LIN XINGYE | Europäisches Patentamt | 2021

    Freier Zugriff

    Applying availability SLAs to traffic management systems

    Stogerer, C. / Brandic, I. / Emeakaroha, V. C. et al. | IEEE | 2011


    4.2 Applying graph theory terms to description of VTS

    Jackowski, K. | British Library Conference Proceedings | 2009