Minimum broadcast time is NP-complete for 3-regular planar graphs and deadline 2
Identifieur interne : 000885 ( Istex/Corpus ); précédent : 000884; suivant : 000886Minimum broadcast time is NP-complete for 3-regular planar graphs and deadline 2
Auteurs : Martin MiddendorfSource :
- Information Processing Letters [ 0020-0190 ] ; 1993.
Abstract
The Minimum Broadcast Time (MBT) problem is whether a piece of information can be disseminated in a graph from a set of source nodes to all other nodes of the graph in at most k time steps. It is assumed that in one time step each node that contains the information can broadcast it to at most one of its neighbours. We show that MBT is NP-complete for 3-regular planar graphs and a constant deadline k⩾2.
Url:
DOI: 10.1016/0020-0190(93)90066-I
Links to Exploration step
ISTEX:893F062F5D8E8DC935ED1BA8DAA1A97C58300D8FLe document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title>Minimum broadcast time is NP-complete for 3-regular planar graphs and deadline 2</title><author><name sortKey="Middendorf, Martin" sort="Middendorf, Martin" uniqKey="Middendorf M" first="Martin" last="Middendorf">Martin Middendorf</name><affiliation><mods:affiliation>Institut für Angewandte Informatik und Formale Beschreibungsverfahren, Universität Karlsruhe, Postfach 6980, W-7500 Karlsruhe, Germany</mods:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:893F062F5D8E8DC935ED1BA8DAA1A97C58300D8F</idno><date when="1993" year="1993">1993</date><idno type="doi">10.1016/0020-0190(93)90066-I</idno><idno type="url">https://api.istex.fr/document/893F062F5D8E8DC935ED1BA8DAA1A97C58300D8F/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">000885</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">000885</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a">Minimum broadcast time is NP-complete for 3-regular planar graphs and deadline 2</title><author><name sortKey="Middendorf, Martin" sort="Middendorf, Martin" uniqKey="Middendorf M" first="Martin" last="Middendorf">Martin Middendorf</name><affiliation><mods:affiliation>Institut für Angewandte Informatik und Formale Beschreibungsverfahren, Universität Karlsruhe, Postfach 6980, W-7500 Karlsruhe, Germany</mods:affiliation></affiliation></author></analytic><monogr></monogr><series><title level="j">Information Processing Letters</title><title level="j" type="abbrev">IPL</title><idno type="ISSN">0020-0190</idno><imprint><publisher>ELSEVIER</publisher><date type="published" when="1993">1993</date><biblScope unit="volume">46</biblScope><biblScope unit="issue">6</biblScope><biblScope unit="page" from="281">281</biblScope><biblScope unit="page" to="287">287</biblScope></imprint><idno type="ISSN">0020-0190</idno></series><idno type="istex">893F062F5D8E8DC935ED1BA8DAA1A97C58300D8F</idno><idno type="DOI">10.1016/0020-0190(93)90066-I</idno><idno type="PII">0020-0190(93)90066-I</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0020-0190</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">The Minimum Broadcast Time (MBT) problem is whether a piece of information can be disseminated in a graph from a set of source nodes to all other nodes of the graph in at most k time steps. It is assumed that in one time step each node that contains the information can broadcast it to at most one of its neighbours. We show that MBT is NP-complete for 3-regular planar graphs and a constant deadline k⩾2.</div></front></TEI><istex><corpusName>elsevier</corpusName><author><json:item><name>Martin Middendorf</name><affiliations><json:string>Institut für Angewandte Informatik und Formale Beschreibungsverfahren, Universität Karlsruhe, Postfach 6980, W-7500 Karlsruhe, Germany</json:string></affiliations></json:item></author><subject><json:item><lang><json:string>eng</json:string></lang><value>Combinatorial optimization</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>information dissemination</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>algorithms</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>graph algorithms</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>NP-completeness</value></json:item></subject><language><json:string>eng</json:string></language><originalGenre><json:string>Full-length article</json:string></originalGenre><abstract>The Minimum Broadcast Time (MBT) problem is whether a piece of information can be disseminated in a graph from a set of source nodes to all other nodes of the graph in at most k time steps. It is assumed that in one time step each node that contains the information can broadcast it to at most one of its neighbours. We show that MBT is NP-complete for 3-regular planar graphs and a constant deadline k⩾2.</abstract><qualityIndicators><score>3.583</score><pdfVersion>1.2</pdfVersion><pdfPageSize>540 x 749 pts</pdfPageSize><refBibsNative>true</refBibsNative><keywordCount>5</keywordCount><abstractCharCount>405</abstractCharCount><pdfWordCount>2671</pdfWordCount><pdfCharCount>14052</pdfCharCount><pdfPageCount>7</pdfPageCount><abstractWordCount>76</abstractWordCount></qualityIndicators><title>Minimum broadcast time is NP-complete for 3-regular planar graphs and deadline 2</title><pii><json:string>0020-0190(93)90066-I</json:string></pii><refBibs><json:item><author><json:item><name>M.E. Dyer</name></json:item><json:item><name>A.M. Frieze</name></json:item></author><host><volume>7</volume><pages><last>184</last><first>174</first></pages><author></author><title>J. Algorithms</title></host><title>Planar 3DM is NP-complete</title></json:item><json:item><host><author></author><title>Computers and Intractability</title></host></json:item><json:item><author><json:item><name>S.M. Hedetniemi</name></json:item><json:item><name>S.T. Hedetniemi</name></json:item><json:item><name>A.L. Listman</name></json:item></author><host><volume>18</volume><pages><last>349</last><first>319</first></pages><author></author><title>Networks</title></host><title>A survey of gossiping and broadcasting in communication networks</title></json:item><json:item><author><json:item><name>A. Jakoby</name></json:item><json:item><name>R. Reischuk</name></json:item><json:item><name>C. Schindelhauer</name></json:item></author><host><author></author><title>Proc. 18th Workshop on Complexity, Efficient Algorithms and Data Structures</title></host><title>MINIMUM BROADCAST TIME for graphs with constant degree</title></json:item><json:item><host><author></author></host></json:item><json:item><author><json:item><name>P.J. Slater</name></json:item><json:item><name>E.J. Cockayne</name></json:item><json:item><name>S.T. Hedetniemi</name></json:item></author><host><volume>10</volume><pages><last>701</last><first>692</first></pages><author></author><title>SIAM J. Comput.</title></host><title>Information dissemination in trees</title></json:item></refBibs><genre><json:string>research-article</json:string></genre><host><volume>46</volume><pii><json:string>S0020-0190(00)X0414-0</json:string></pii><pages><last>287</last><first>281</first></pages><issn><json:string>0020-0190</json:string></issn><issue>6</issue><genre><json:string>journal</json:string></genre><language><json:string>unknown</json:string></language><title>Information Processing Letters</title><publicationDate>1993</publicationDate></host><categories><wos><json:string>science</json:string><json:string>computer science, information systems</json:string></wos><scienceMetrix><json:string>applied sciences</json:string><json:string>information & communication technologies</json:string><json:string>computation theory & mathematics</json:string></scienceMetrix></categories><publicationDate>1993</publicationDate><copyrightDate>1993</copyrightDate><doi><json:string>10.1016/0020-0190(93)90066-I</json:string></doi><id>893F062F5D8E8DC935ED1BA8DAA1A97C58300D8F</id><score>0.032462608</score><fulltext><json:item><extension>pdf</extension><original>true</original><mimetype>application/pdf</mimetype><uri>https://api.istex.fr/document/893F062F5D8E8DC935ED1BA8DAA1A97C58300D8F/fulltext/pdf</uri></json:item><json:item><extension>zip</extension><original>false</original><mimetype>application/zip</mimetype><uri>https://api.istex.fr/document/893F062F5D8E8DC935ED1BA8DAA1A97C58300D8F/fulltext/zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/document/893F062F5D8E8DC935ED1BA8DAA1A97C58300D8F/fulltext/tei"><teiHeader><fileDesc><titleStmt><title level="a">Minimum broadcast time is NP-complete for 3-regular planar graphs and deadline 2</title></titleStmt><publicationStmt><authority>ISTEX</authority><publisher>ELSEVIER</publisher><availability><p>ELSEVIER</p></availability><date>1993</date></publicationStmt><notesStmt><note>Communicated by T. Lengauer</note></notesStmt><sourceDesc><biblStruct type="inbook"><analytic><title level="a">Minimum broadcast time is NP-complete for 3-regular planar graphs and deadline 2</title><author xml:id="author-1"><persName><forename type="first">Martin</forename><surname>Middendorf</surname></persName><note type="correspondence"><p>Correspondence to: Dr. M. Middendorf, Institut für Angewandte Informatik und Formale Beschreibungsverfahren, Universität Karlsruhe, Postfach 6980, W-7500 Karlsruhe, Germany.</p></note><affiliation>Institut für Angewandte Informatik und Formale Beschreibungsverfahren, Universität Karlsruhe, Postfach 6980, W-7500 Karlsruhe, Germany</affiliation></author></analytic><monogr><title level="j">Information Processing Letters</title><title level="j" type="abbrev">IPL</title><idno type="pISSN">0020-0190</idno><idno type="PII">S0020-0190(00)X0414-0</idno><imprint><publisher>ELSEVIER</publisher><date type="published" when="1993"></date><biblScope unit="volume">46</biblScope><biblScope unit="issue">6</biblScope><biblScope unit="page" from="281">281</biblScope><biblScope unit="page" to="287">287</biblScope></imprint></monogr><idno type="istex">893F062F5D8E8DC935ED1BA8DAA1A97C58300D8F</idno><idno type="DOI">10.1016/0020-0190(93)90066-I</idno><idno type="PII">0020-0190(93)90066-I</idno></biblStruct></sourceDesc></fileDesc><profileDesc><creation><date>1993</date></creation><langUsage><language ident="en">en</language></langUsage><abstract xml:lang="en"><p>The Minimum Broadcast Time (MBT) problem is whether a piece of information can be disseminated in a graph from a set of source nodes to all other nodes of the graph in at most k time steps. It is assumed that in one time step each node that contains the information can broadcast it to at most one of its neighbours. We show that MBT is NP-complete for 3-regular planar graphs and a constant deadline k⩾2.</p></abstract><textClass><keywords scheme="keyword"><list><head>Keywords</head><item><term>Combinatorial optimization</term></item><item><term>information dissemination</term></item><item><term>algorithms</term></item><item><term>graph algorithms</term></item><item><term>NP-completeness</term></item></list></keywords></textClass></profileDesc><revisionDesc><change when="1993-03-22">Modified</change><change when="1993">Published</change></revisionDesc></teiHeader></istex:fulltextTEI><json:item><extension>txt</extension><original>false</original><mimetype>text/plain</mimetype><uri>https://api.istex.fr/document/893F062F5D8E8DC935ED1BA8DAA1A97C58300D8F/fulltext/txt</uri></json:item></fulltext><metadata><istex:metadataXml wicri:clean="Elsevier, elements deleted: tail"><istex:xmlDeclaration>version="1.0" encoding="utf-8"</istex:xmlDeclaration><istex:docType PUBLIC="-//ES//DTD journal article DTD version 4.5.2//EN//XML" URI="art452.dtd" name="istex:docType"></istex:docType><istex:document><converted-article version="4.5.2" docsubtype="fla"><item-info><jid>IPL</jid><aid>9390066I</aid><ce:pii>0020-0190(93)90066-I</ce:pii><ce:doi>10.1016/0020-0190(93)90066-I</ce:doi><ce:copyright type="unknown" year="1993"></ce:copyright></item-info><head><ce:title>Minimum broadcast time is NP-complete for 3-regular planar graphs and deadline 2</ce:title><ce:author-group><ce:author><ce:given-name>Martin</ce:given-name><ce:surname>Middendorf</ce:surname><ce:cross-ref refid="COR1"><ce:sup>∗</ce:sup></ce:cross-ref></ce:author><ce:affiliation><ce:textfn>Institut für Angewandte Informatik und Formale Beschreibungsverfahren, Universität Karlsruhe, Postfach 6980, W-7500 Karlsruhe, Germany</ce:textfn></ce:affiliation><ce:correspondence id="COR1"><ce:label>∗</ce:label><ce:text>Correspondence to: Dr. M. Middendorf, Institut für Angewandte Informatik und Formale Beschreibungsverfahren, Universität Karlsruhe, Postfach 6980, W-7500 Karlsruhe, Germany.</ce:text></ce:correspondence></ce:author-group><ce:date-received day="17" month="11" year="1992"></ce:date-received><ce:date-revised day="22" month="3" year="1993"></ce:date-revised><ce:miscellaneous>Communicated by T. Lengauer</ce:miscellaneous><ce:abstract><ce:section-title>Abstract</ce:section-title><ce:abstract-sec><ce:simple-para>The Minimum Broadcast Time (MBT) problem is whether a piece of information can be disseminated in a graph from a set of source nodes to all other nodes of the graph in at most <ce:italic>k</ce:italic> time steps. It is assumed that in one time step each node that contains the information can broadcast it to at most one of its neighbours. We show that MBT is NP-complete for 3-regular planar graphs and a constant deadline <ce:italic>k</ce:italic>⩾2.</ce:simple-para></ce:abstract-sec></ce:abstract><ce:keywords><ce:section-title>Keywords</ce:section-title><ce:keyword><ce:text>Combinatorial optimization</ce:text></ce:keyword><ce:keyword><ce:text>information dissemination</ce:text></ce:keyword><ce:keyword><ce:text>algorithms</ce:text></ce:keyword><ce:keyword><ce:text>graph algorithms</ce:text></ce:keyword><ce:keyword><ce:text>NP-completeness</ce:text></ce:keyword></ce:keywords></head></converted-article></istex:document></istex:metadataXml><mods version="3.6"><titleInfo><title>Minimum broadcast time is NP-complete for 3-regular planar graphs and deadline 2</title></titleInfo><titleInfo type="alternative" contentType="CDATA"><title>Minimum broadcast time is NP-complete for 3-regular planar graphs and deadline 2</title></titleInfo><name type="personal"><namePart type="given">Martin</namePart><namePart type="family">Middendorf</namePart><affiliation>Institut für Angewandte Informatik und Formale Beschreibungsverfahren, Universität Karlsruhe, Postfach 6980, W-7500 Karlsruhe, Germany</affiliation><description>Correspondence to: Dr. M. Middendorf, Institut für Angewandte Informatik und Formale Beschreibungsverfahren, Universität Karlsruhe, Postfach 6980, W-7500 Karlsruhe, Germany.</description><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre type="research-article" displayLabel="Full-length article"></genre><originInfo><publisher>ELSEVIER</publisher><dateIssued encoding="w3cdtf">1993</dateIssued><dateModified encoding="w3cdtf">1993-03-22</dateModified><copyrightDate encoding="w3cdtf">1993</copyrightDate></originInfo><language><languageTerm type="code" authority="iso639-2b">eng</languageTerm><languageTerm type="code" authority="rfc3066">en</languageTerm></language><physicalDescription><internetMediaType>text/html</internetMediaType></physicalDescription><abstract lang="en">The Minimum Broadcast Time (MBT) problem is whether a piece of information can be disseminated in a graph from a set of source nodes to all other nodes of the graph in at most k time steps. It is assumed that in one time step each node that contains the information can broadcast it to at most one of its neighbours. We show that MBT is NP-complete for 3-regular planar graphs and a constant deadline k⩾2.</abstract><note>Communicated by T. Lengauer</note><subject><genre>Keywords</genre><topic>Combinatorial optimization</topic><topic>information dissemination</topic><topic>algorithms</topic><topic>graph algorithms</topic><topic>NP-completeness</topic></subject><relatedItem type="host"><titleInfo><title>Information Processing Letters</title></titleInfo><titleInfo type="abbreviated"><title>IPL</title></titleInfo><genre type="journal">journal</genre><originInfo><dateIssued encoding="w3cdtf">19930726</dateIssued></originInfo><identifier type="ISSN">0020-0190</identifier><identifier type="PII">S0020-0190(00)X0414-0</identifier><part><date>19930726</date><detail type="volume"><number>46</number><caption>vol.</caption></detail><detail type="issue"><number>6</number><caption>no.</caption></detail><extent unit="issue pages"><start>263</start><end>314</end></extent><extent unit="pages"><start>281</start><end>287</end></extent></part></relatedItem><identifier type="istex">893F062F5D8E8DC935ED1BA8DAA1A97C58300D8F</identifier><identifier type="DOI">10.1016/0020-0190(93)90066-I</identifier><identifier type="PII">0020-0190(93)90066-I</identifier><recordInfo><recordContentSource>ELSEVIER</recordContentSource></recordInfo></mods></metadata><serie></serie></istex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Istex/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000885 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 000885 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Rhénanie
|area= UnivTrevesV1
|flux= Istex
|étape= Corpus
|type= RBID
|clé= ISTEX:893F062F5D8E8DC935ED1BA8DAA1A97C58300D8F
|texte= Minimum broadcast time is NP-complete for 3-regular planar graphs and deadline 2
}}
| This area was generated with Dilib version V0.6.31. |  |