Maximum covering with D-cliques

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

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    5 Citations (Scopus)

    Abstract

    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.

    Original languageEnglish
    Title of host publicationFundamentals of Computation Theory : Proceedings 9th International Conference, FCT'93, Szeged, Hungary, August 23-27, 1993
    EditorsZ. Ésik
    Place of PublicationBerlin
    PublisherSpringer
    Pages319-328
    ISBN (Electronic)978-3-540-47923-9
    ISBN (Print)978-3-540-57163-6
    DOIs
    Publication statusPublished - 1993
    Event9th International Conference Fundamentals of Computer Science (FCT'93), August 23-27, 1993, Szeged, Hungary - Szeged, Hungary
    Duration: 23 Aug 199327 Aug 1993

    Publication series

    NameLecture Notes in Computer Science
    Volume710
    ISSN (Print)0302-9743

    Conference

    Conference9th International Conference Fundamentals of Computer Science (FCT'93), August 23-27, 1993, Szeged, Hungary
    Abbreviated titleFCT'93
    Country/TerritoryHungary
    CitySzeged
    Period23/08/9327/08/93

    Fingerprint

    Dive into the research topics of 'Maximum covering with D-cliques'. Together they form a unique fingerprint.

    Cite this