Maximum covering with D-cliques

K. Jansen, P. Scheffler, G.J. Woeginger

    Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

    5 Citaten (Scopus)

    Samenvatting

    Given a graph G = (V, E), we consider the problem to find a set of D pairwise disjoint cliques in it with maximum overall number of vertices. We determine the computational complexity of this problem restricted to a variety of different graph classes. We give polynomial time algorithms for the problem restricted to interval graphs, bipartite graphs, cographs, directed path graphs and partial k-trees. In contrast, we show the NP-completeness for undirected path graphs.

    Originele taal-2Engels
    TitelFundamentals of Computation Theory : Proceedings 9th International Conference, FCT'93, Szeged, Hungary, August 23-27, 1993
    RedacteurenZ. Ésik
    Plaats van productieBerlin
    UitgeverijSpringer
    Pagina's319-328
    ISBN van elektronische versie978-3-540-47923-9
    ISBN van geprinte versie978-3-540-57163-6
    DOI's
    StatusGepubliceerd - 1993
    Evenement9th International Conference Fundamentals of Computer Science (FCT'93), August 23-27, 1993, Szeged, Hungary - Szeged, Hongarije
    Duur: 23 aug 199327 aug 1993

    Publicatie series

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

    Congres

    Congres9th International Conference Fundamentals of Computer Science (FCT'93), August 23-27, 1993, Szeged, Hungary
    Verkorte titelFCT'93
    Land/RegioHongarije
    StadSzeged
    Periode23/08/9327/08/93

    Vingerafdruk

    Duik in de onderzoeksthema's van 'Maximum covering with D-cliques'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit