Coherent network partitions
- We continue to study coherent partitions of graphs whereby the vertex set is partitioned into subsets that induce biclique spanned subgraphs. The problem of identifying the minimum number of edges to obtain biclique spanned connected components (CNP), called the coherence number, is NP-hard even on bipartite graphs. Here, we propose a graph transformation geared towards obtaining an O (log n)-approximation algorithm for the CNP on a bipartite graph with n vertices. The transformation is inspired by a new characterization of biclique spanned subgraphs. In addition, we study coherent partitions on prime graphs, and show that finding coherent partitions reduces to the problem of finding coherent partitions in a prime graph. Therefore, these results provide future directions for approximation algorithms for the coherence number of a given graph.
Verfasserangaben: | Angela Angeleska, Sara OmranianORCiDGND, Zoran NikoloskiORCiDGND |
---|---|
DOI: | https://doi.org/10.1016/j.tcs.2021.10.002 |
ISSN: | 0304-3975 |
Titel des übergeordneten Werks (Englisch): | Theoretical computer science : the journal of the EATCS |
Untertitel (Englisch): | Characterizations with cographs and prime graphs |
Verlag: | Elsevier |
Verlagsort: | Amsterdam [u.a.] |
Publikationstyp: | Wissenschaftlicher Artikel |
Sprache: | Englisch |
Datum der Erstveröffentlichung: | 11.10.2021 |
Erscheinungsjahr: | 2021 |
Datum der Freischaltung: | 01.03.2024 |
Freies Schlagwort / Tag: | Cographs; Coherent partition; Graph partitions; Network clustering; Prime graphs |
Band: | 894 |
Seitenanzahl: | 9 |
Erste Seite: | 3 |
Letzte Seite: | 11 |
Fördernde Institution: | University of Tampa Research Excellence and Scholarly Innovation Award/Dana Foundation Grant |
Organisationseinheiten: | Mathematisch-Naturwissenschaftliche Fakultät / Institut für Biochemie und Biologie |
DDC-Klassifikation: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik |
Peer Review: | Referiert |