The Domatic Partition Problem in Separable Graphs

The domatic partition problem consists of partitioning a given graph into a maximum number of disjoint dominating sets. This problem is related with the domatic number problem, which consists of quantifying this maximum number of disjoint dominating sets. Both problems were proved to be NP-complete....

Full description

Saved in:
Bibliographic Details
Published in:Mathematics (Basel) 2022-02, Vol.10 (4), p.640
Main Authors: Landete, Mercedes, Sainz-Pardo, José Luis
Format: Article
Language:English
Subjects:
Algorithms
Decomposition
decomposition algorithm
domatic number
domatic partition
Food science
Graphs
graphs with blocks
integer linear problem
Integer programming
Partitions (mathematics)
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c367t-50d7c8b1f3d6c388484c2a649abd30967757d980e6bea7cb80e0dc8d16a400f53
cites cdi_FETCH-LOGICAL-c367t-50d7c8b1f3d6c388484c2a649abd30967757d980e6bea7cb80e0dc8d16a400f53
container_end_page
container_issue 4
container_start_page 640
container_title Mathematics (Basel)
container_volume 10
creator Landete, Mercedes
Sainz-Pardo, José Luis
description The domatic partition problem consists of partitioning a given graph into a maximum number of disjoint dominating sets. This problem is related with the domatic number problem, which consists of quantifying this maximum number of disjoint dominating sets. Both problems were proved to be NP-complete. In this paper, we present a decomposition algorithm for finding a domatic partition on separable graphs, that is, on graphs with blocks, and as a consequence, its domatic number, highly reducing the computational complexity. Computational results illustrate the benefits of the block decomposition algorithm.
doi_str_mv 10.3390/math10040640
format article
fullrecord <record><control><sourceid>proquest_doaj_</sourceid><recordid>TN_cdi_doaj_primary_oai_doaj_org_article_fcf75cd6bd304081a30a8ba7d1ff72d2</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><doaj_id>oai_doaj_org_article_fcf75cd6bd304081a30a8ba7d1ff72d2</doaj_id><sourcerecordid>2633111316</sourcerecordid><originalsourceid>FETCH-LOGICAL-c367t-50d7c8b1f3d6c388484c2a649abd30967757d980e6bea7cb80e0dc8d16a400f53</originalsourceid><addsrcrecordid>eNpNUE1PwzAMjRBITGM3fkAlrhScJk3SIxowkCYxiXGO3HywTttSku7AvydjCM0XP9vPz08m5JrCHWMN3G9xWFEADoLDGRlVVSVLmQfnJ_iSTFJaQ46GMsWbEaHLlSseQ17uTLHAOHRDF3bFIoZ247ZFtyveXY8Rc1XMIvardEUuPG6Sm_zlMfl4flpOX8r52-x1-jAvDRNyKGuw0qiWemaFYUpxxU2FgjfYWgaNkLKWtlHgROtQmjYjsEZZKpAD-JqNyetR1wZc6z52W4zfOmCnfxshfuqDXbNx2hsva2PFQZmDosgAVYvSUu9lZausdXPU6mP42rs06HXYx122ryvBGKWUUZFZt0eWiSGl6Pz_VQr68GN9-mP2A5-lbRg</addsrcrecordid><sourcetype>Open Website</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2633111316</pqid></control><display><type>article</type><title>The Domatic Partition Problem in Separable Graphs</title><source>Publicly Available Content Database</source><creator>Landete, Mercedes ; Sainz-Pardo, José Luis</creator><creatorcontrib>Landete, Mercedes ; Sainz-Pardo, José Luis</creatorcontrib><description>The domatic partition problem consists of partitioning a given graph into a maximum number of disjoint dominating sets. This problem is related with the domatic number problem, which consists of quantifying this maximum number of disjoint dominating sets. Both problems were proved to be NP-complete. In this paper, we present a decomposition algorithm for finding a domatic partition on separable graphs, that is, on graphs with blocks, and as a consequence, its domatic number, highly reducing the computational complexity. Computational results illustrate the benefits of the block decomposition algorithm.</description><identifier>ISSN: 2227-7390</identifier><identifier>EISSN: 2227-7390</identifier><identifier>DOI: 10.3390/math10040640</identifier><language>eng</language><publisher>Basel: MDPI AG</publisher><subject>Algorithms ; Decomposition ; decomposition algorithm ; domatic number ; domatic partition ; Food science ; Graphs ; graphs with blocks ; integer linear problem ; Integer programming ; Partitions (mathematics)</subject><ispartof>Mathematics (Basel), 2022-02, Vol.10 (4), p.640</ispartof><rights>2022 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c367t-50d7c8b1f3d6c388484c2a649abd30967757d980e6bea7cb80e0dc8d16a400f53</citedby><cites>FETCH-LOGICAL-c367t-50d7c8b1f3d6c388484c2a649abd30967757d980e6bea7cb80e0dc8d16a400f53</cites><orcidid>0000-0002-2663-9967 ; 0000-0002-5201-0476</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktopdf>$$Uhttps://www.proquest.com/docview/2633111316/fulltextPDF?pq-origsite=primo$$EPDF$$P50$$Gproquest$$Hfree_for_read</linktopdf><linktohtml>$$Uhttps://www.proquest.com/docview/2633111316?pq-origsite=primo$$EHTML$$P50$$Gproquest$$Hfree_for_read</linktohtml><link.rule.ids>314,780,784,25753,27924,27925,37012,44590,75126</link.rule.ids></links><search><creatorcontrib>Landete, Mercedes</creatorcontrib><creatorcontrib>Sainz-Pardo, José Luis</creatorcontrib><title>The Domatic Partition Problem in Separable Graphs</title><title>Mathematics (Basel)</title><description>The domatic partition problem consists of partitioning a given graph into a maximum number of disjoint dominating sets. This problem is related with the domatic number problem, which consists of quantifying this maximum number of disjoint dominating sets. Both problems were proved to be NP-complete. In this paper, we present a decomposition algorithm for finding a domatic partition on separable graphs, that is, on graphs with blocks, and as a consequence, its domatic number, highly reducing the computational complexity. Computational results illustrate the benefits of the block decomposition algorithm.</description><subject>Algorithms</subject><subject>Decomposition</subject><subject>decomposition algorithm</subject><subject>domatic number</subject><subject>domatic partition</subject><subject>Food science</subject><subject>Graphs</subject><subject>graphs with blocks</subject><subject>integer linear problem</subject><subject>Integer programming</subject><subject>Partitions (mathematics)</subject><issn>2227-7390</issn><issn>2227-7390</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2022</creationdate><recordtype>article</recordtype><sourceid>PIMPY</sourceid><sourceid>DOA</sourceid><recordid>eNpNUE1PwzAMjRBITGM3fkAlrhScJk3SIxowkCYxiXGO3HywTttSku7AvydjCM0XP9vPz08m5JrCHWMN3G9xWFEADoLDGRlVVSVLmQfnJ_iSTFJaQ46GMsWbEaHLlSseQ17uTLHAOHRDF3bFIoZ247ZFtyveXY8Rc1XMIvardEUuPG6Sm_zlMfl4flpOX8r52-x1-jAvDRNyKGuw0qiWemaFYUpxxU2FgjfYWgaNkLKWtlHgROtQmjYjsEZZKpAD-JqNyetR1wZc6z52W4zfOmCnfxshfuqDXbNx2hsva2PFQZmDosgAVYvSUu9lZausdXPU6mP42rs06HXYx122ryvBGKWUUZFZt0eWiSGl6Pz_VQr68GN9-mP2A5-lbRg</recordid><startdate>20220201</startdate><enddate>20220201</enddate><creator>Landete, Mercedes</creator><creator>Sainz-Pardo, José Luis</creator><general>MDPI AG</general><scope>AAYXX</scope><scope>CITATION</scope><scope>3V.</scope><scope>7SC</scope><scope>7TB</scope><scope>7XB</scope><scope>8AL</scope><scope>8FD</scope><scope>8FE</scope><scope>8FG</scope><scope>8FK</scope><scope>ABJCF</scope><scope>ABUWG</scope><scope>AFKRA</scope><scope>ARAPS</scope><scope>AZQEC</scope><scope>BENPR</scope><scope>BGLVJ</scope><scope>CCPQU</scope><scope>DWQXO</scope><scope>FR3</scope><scope>GNUQQ</scope><scope>HCIFZ</scope><scope>JQ2</scope><scope>K7-</scope><scope>KR7</scope><scope>L6V</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope><scope>M0N</scope><scope>M7S</scope><scope>P62</scope><scope>PIMPY</scope><scope>PQEST</scope><scope>PQQKQ</scope><scope>PQUKI</scope><scope>PRINS</scope><scope>PTHSS</scope><scope>Q9U</scope><scope>DOA</scope><orcidid>https://orcid.org/0000-0002-2663-9967</orcidid><orcidid>https://orcid.org/0000-0002-5201-0476</orcidid></search><sort><creationdate>20220201</creationdate><title>The Domatic Partition Problem in Separable Graphs</title><author>Landete, Mercedes ; Sainz-Pardo, José Luis</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c367t-50d7c8b1f3d6c388484c2a649abd30967757d980e6bea7cb80e0dc8d16a400f53</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2022</creationdate><topic>Algorithms</topic><topic>Decomposition</topic><topic>decomposition algorithm</topic><topic>domatic number</topic><topic>domatic partition</topic><topic>Food science</topic><topic>Graphs</topic><topic>graphs with blocks</topic><topic>integer linear problem</topic><topic>Integer programming</topic><topic>Partitions (mathematics)</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Landete, Mercedes</creatorcontrib><creatorcontrib>Sainz-Pardo, José Luis</creatorcontrib><collection>CrossRef</collection><collection>ProQuest Central (Corporate)</collection><collection>Computer and Information Systems Abstracts</collection><collection>Mechanical &amp; Transportation Engineering Abstracts</collection><collection>ProQuest Central (purchase pre-March 2016)</collection><collection>Computing Database (Alumni Edition)</collection><collection>Technology Research Database</collection><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>ProQuest Central (Alumni) (purchase pre-March 2016)</collection><collection>Materials Science &amp; Engineering Collection</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central</collection><collection>Advanced Technologies &amp; Aerospace Collection</collection><collection>ProQuest Central Essentials</collection><collection>ProQuest Central</collection><collection>Technology Collection</collection><collection>ProQuest One Community College</collection><collection>ProQuest Central</collection><collection>Engineering Research Database</collection><collection>ProQuest Central Student</collection><collection>SciTech Premium Collection</collection><collection>ProQuest Computer Science Collection</collection><collection>Computer Science Database</collection><collection>Civil Engineering Abstracts</collection><collection>ProQuest Engineering Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><collection>Computing Database</collection><collection>Engineering Database</collection><collection>ProQuest Advanced Technologies &amp; Aerospace Collection</collection><collection>Publicly Available Content Database</collection><collection>ProQuest One Academic Eastern Edition (DO NOT USE)</collection><collection>ProQuest One Academic</collection><collection>ProQuest One Academic UKI Edition</collection><collection>ProQuest Central China</collection><collection>Engineering Collection</collection><collection>ProQuest Central Basic</collection><collection>Directory of Open Access Journals</collection><jtitle>Mathematics (Basel)</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Landete, Mercedes</au><au>Sainz-Pardo, José Luis</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>The Domatic Partition Problem in Separable Graphs</atitle><jtitle>Mathematics (Basel)</jtitle><date>2022-02-01</date><risdate>2022</risdate><volume>10</volume><issue>4</issue><spage>640</spage><pages>640-</pages><issn>2227-7390</issn><eissn>2227-7390</eissn><abstract>The domatic partition problem consists of partitioning a given graph into a maximum number of disjoint dominating sets. This problem is related with the domatic number problem, which consists of quantifying this maximum number of disjoint dominating sets. Both problems were proved to be NP-complete. In this paper, we present a decomposition algorithm for finding a domatic partition on separable graphs, that is, on graphs with blocks, and as a consequence, its domatic number, highly reducing the computational complexity. Computational results illustrate the benefits of the block decomposition algorithm.</abstract><cop>Basel</cop><pub>MDPI AG</pub><doi>10.3390/math10040640</doi><orcidid>https://orcid.org/0000-0002-2663-9967</orcidid><orcidid>https://orcid.org/0000-0002-5201-0476</orcidid><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 2227-7390
ispartof Mathematics (Basel), 2022-02, Vol.10 (4), p.640
issn 2227-7390
2227-7390
language eng
recordid cdi_doaj_primary_oai_doaj_org_article_fcf75cd6bd304081a30a8ba7d1ff72d2
source Publicly Available Content Database
subjects Algorithms
Decomposition
decomposition algorithm
domatic number
domatic partition
Food science
Graphs
graphs with blocks
integer linear problem
Integer programming
Partitions (mathematics)
title The Domatic Partition Problem in Separable Graphs
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-04T22%3A35%3A52IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_doaj_&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=The%20Domatic%20Partition%20Problem%20in%20Separable%20Graphs&rft.jtitle=Mathematics%20(Basel)&rft.au=Landete,%20Mercedes&rft.date=2022-02-01&rft.volume=10&rft.issue=4&rft.spage=640&rft.pages=640-&rft.issn=2227-7390&rft.eissn=2227-7390&rft_id=info:doi/10.3390/math10040640&rft_dat=%3Cproquest_doaj_%3E2633111316%3C/proquest_doaj_%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c367t-50d7c8b1f3d6c388484c2a649abd30967757d980e6bea7cb80e0dc8d16a400f53%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2633111316&rft_id=info:pmid/&rfr_iscdi=true