Exact algorithms for dominating clique problems

Full text not available from this repository. Send a request to the author for a copy of the paper
Item Type: Proceeding
MIUR type: Proceedings > Proceedings
Title: Exact algorithms for dominating clique problems
Authors string: N. Bourgeois; Della Croce Di Dojola F.; B. Escoffier; V.T. Paschos
University authors:
Page Range: pp. 4-13
Journal or Publication Title: LECTURE NOTES IN COMPUTER SCIENCE
Referee type: Not specified type
Publisher: Springer
ISBN: 03029743161
ISSN: 0302-9743
Volume: 5878
Event Title: 20th International Symposium, ISAAC 2009
Event Location: Honolulu, Hawaii (USA)
Event Dates: December 16-18, 2009
Abstract: We handle in this paper three dominating clique problems, namely, the decision problem itself when one asks if there exists a dominating clique in a graph G and two optimization versions where one asks for a maximum- and a minimum-size dominating clique, if any. For the three problems we propose optimal algorithms with provably worst-case upper bounds improving existing ones by (D. Kratsch and M. Liedloff, An exact algorithm for the minimum dominating clique problem, Theoretical Computer Science 385(1-3), pp. 226-240, 2007). We then settle all the three problems in sparse and dense graphs also providing improved upper running time bounds
Date: 2009
Status: Published
Language of publication: English
Uncontrolled Keywords:
Departments (original): DAUIN - Control and Computer Engineering
Departments: DAUIN - Department of Control and Computer Engineering
Related URLs:
    Subjects: Area 01 - Scienze matematiche e informatiche > RICERCA OPERATIVA
    Date Deposited: 14 Jan 2010 18:01
    Last Modified: 11 Jul 2014 00:05
    Id Number (DOI): 10.1007/978-3-642-10631-6_3
    Permalink: http://porto.polito.it/id/eprint/2302842
    Linksolver URL: Linksolver link
    Citations:

    This field presents the citations number present on Scopus and Web of Science databases e links to the remote records. Also Google Scholar link is present.

    There may be discrepancies with respect to the data in databases for the following reasons:

    • Differences from fields (title, year,...) in UGOV and those in the databases.
    • PORTO citations are extracted monthly. The db is in real time
    • The WoS citation number reflect the collections subscribed by Politecnico (Science citation index Expanded and Conference Proceedings Citation Index)

    For informations contact scrivia/porto

    +
    -

    Actions (login required)

    View Item View Item