{"@context":["https://w3id.org/fdo/context/v1",{"schema":"https://schema.org/","prov":"http://www.w3.org/ns/prov#","fdo":"https://w3id.org/fdo/vocabulary/"}],"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q856876","@type":"DigitalObject","kernel":{"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q856876","digitalObjectType":"https://schema.org/ScholarlyArticle","primaryIdentifier":"mardi:Q856876","kernelVersion":"v1","immutable":true,"modified":"2026-01-12T11:59:47Z"},"profile":{"@context":"https://schema.org","@type":"ScholarlyArticle","@id":"https://portal.mardi4nfdi.de/entity/Q856876","name":"Optimal broadcast domination in polynomial time","headline":"Optimal broadcast domination in polynomial time","description":"scientific article; zbMATH DE number 5080069","url":"https://portal.mardi4nfdi.de/entity/Q856876","datePublished":"2006-12-14","author":[{"@id":"https://portal.mardi4nfdi.de/entity/Q266929"},{"@id":"https://portal.mardi4nfdi.de/entity/Q270004"}],"publisher":[{"@id":"https://portal.mardi4nfdi.de/entity/Q175483"}],"identifier":{"@type":"PropertyValue","propertyID":"doi","value":"10.1016/J.DISC.2006.06.013","url":"https://doi.org/10.1016/J.DISC.2006.06.013"},"sameAs":["https://doi.org/10.1016/J.DISC.2006.06.013"],"comment":"From the authors' abstract: Broadcast domination was introduced in 2002 as a variant of the standard domination problem such that different vertices can be assigned different domination powers. Since the presentation of the problem its computational complexity has been open, and the general belief has been that it might be NP-hard. In this paper, it is shown that it is in P.","citation":[{"@id":"https://portal.mardi4nfdi.de/entity/Q4275335"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4677956"},{"@id":"https://portal.mardi4nfdi.de/entity/Q2581560"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4821947"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4158479"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4368729"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4368728"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5897555"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4378634"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5581642"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3291034"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4119239"}]},"provenance":{"prov:generatedAtTime":"2026-01-12T11:59:47Z","prov:wasAttributedTo":"MaRDI Knowledge Graph"}}