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.


    Access

    Access via TIB

    Check availability in my library


    Export, share and cite



    Title :

    Applying Graph Theory to Problems in Air Traffic Management


    Contributors:

    Conference:

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


    Publication date :

    2017-06-05


    Type of media :

    Miscellaneous


    Type of material :

    No indication


    Language :

    English




    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 | European Patent Office | 2021

    Free access

    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