Acyclic domination on bipartite permutation graphs

DOI10.1016/J.IPL.2006.04.002MaRDI QIDQ845701zbMATH OpenOpenAlexFDO

Authors Guangjun Xu, Erfang Shan, Liying Kang

Publication date 29 January 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2006.04.002

zbMATH Keywords

acyclic dominating setalgorithmsbipartite permutation graphdominating set

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Algorithm of acyclic dominating set problem on bipartite permutation graphs
• An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs
• Edge domination on bipartite permutation graphs and cotriangulated graphs
• Acyclic domination
• Complementary acyclic domination in graphs

Cites work

• Acyclic domination
• An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs
• Bipartite permutation graphs
• Edge domination on bipartite permutation graphs and cotriangulated graphs
• Graph theory
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• Solving the weighted efficient edge domination problem on bipartite permutation graphs
• Weighted efficient domination problem on some perfect graphs

Cited in

(9)

• A polynomial-time algorithm for the paired-domination problem on permutation graphs
• Labeling bipartite permutation graphs with a condition at distance two
• Parameterized domination in circle graphs
• Acyclically pushable bipartite permutation digraphs: an algorithm
• Acyclic total dominating sets in cubic graphs
• Algorithm of acyclic dominating set problem on bipartite permutation graphs
• Acyclic dominating partitions
• Edge domination on bipartite permutation graphs and cotriangulated graphs
• The rook problem on saw-toothed chessboards

This page was built for publication: Acyclic domination on bipartite permutation graphs

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