Configurations with few crossings in topological graphs

C. Knauer, É. Schramm, A. Spillner, A. Wolff

    Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

    2 Citaten (Scopus)

    Samenvatting

    In this paper we study the problem of computing subgraphs of a certain configuration in a given topological graph G such that the number of crossings in the subgraph is minimum. The configurations that we consider are spanning trees, s–t paths, cycles, matchings, and ¿-factors for ¿ ¿ {1,2}. We show that it is NP-hard to approximate the minimum number of crossings for these configurations within a factor of k 1¿-¿e for any e > 0, where k is the number of crossings in G. We then show that the problems are fixed-parameter tractable if we use the number of crossings in the given graph as the parameter. Finally we present a simple but effective heuristic for spanning trees.
    Originele taal-2Engels
    TitelAlgorithms and computation : 16th international symposium, ISAAC2005, Sanya, Hainan, China, December 19-21, 2005 : proceedings
    RedacteurenX. Deng, D.Z. Du
    Plaats van productieBerlin
    UitgeverijSpringer
    Pagina's604-613
    ISBN van geprinte versie3-540-30935-7
    DOI's
    StatusGepubliceerd - 2005

    Publicatie series

    NaamLecture Notes in Computer Science
    Volume3827
    ISSN van geprinte versie0302-9743

    Vingerafdruk Duik in de onderzoeksthema's van 'Configurations with few crossings in topological graphs'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit