An efficient algorithm for mixed domination on generalized series-parallel graphs

DOI10.29252/ASTA.5.1.23MaRDI QIDQ5124564zbMATH OpenOpenAlexWikidataFDO

Authors

Publication date 30 September 2020

Published in Algebraic structures and their applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1708.00240

zbMATH Keywords

generalized series-parallelmixed dominating setparse treetree-width

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Abstract: A mixed dominating set $S$ of a graph $G=(V,E)$ is a subset $SsubseteqVcupE$ such that each element $vin(VcupE)setminusS$ is adjacent or incident to at least one element in $S$. The mixed domination number $gamm{a}_m(G)$ of a graph $G$ is the minimum cardinality among all mixed dominating sets in $G$. The problem of finding $gamm{a}_m(G)$ is know to be NP-complete. In this paper, we present an explicit polynomial-time algorithm to construct a mixed dominating set of size $gamm{a}_m(G)$ by a parse tree when $G$ is a generalized series-parallel graph.

Recommendations

• The algorithmic complexity of mixed domination in graphs
• Mixed domination in undirected path graphs and block graphs
• On the mixed domination problem in graphs
• On fixed-parameter tractability of the mixed domination problem for graphs with bounded tree-width
• New algorithms for mixed dominating set

Cited in

(8)

• On the mixed domination problem in graphs
• Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph
• Mixed domination in undirected path graphs and block graphs
• On fixed-parameter tractability of the mixed domination problem for graphs with bounded tree-width
• scientific article; zbMATH DE number 841565 (Why is no real title available?)
• On simultaneous domination and mixed connectivity in graphs
• The algorithmic complexity of mixed domination in graphs
• scientific article; zbMATH DE number 7764100 (Why is no real title available?)

This page was built for publication: An efficient algorithm for mixed domination on generalized series-parallel graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5124564)