Acyclic domination on bipartite permutation graphs

DOI10.1016/j.ipl.2006.04.002zbMath1184.05092OpenAlexW1990345395MaRDI QIDQ845701

Guangjun Xu, Erfang Shan, Li-ying 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

algorithmsdominating setbipartite permutation graphacyclic dominating set

Mathematics Subject Classification ID

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

Related Items

The rook problem on saw-toothed chessboards ⋮ Parameterized domination in circle graphs ⋮ A polynomial-time algorithm for the paired-domination problem on permutation graphs ⋮ Labeling bipartite permutation graphs with a condition at distance two ⋮ Acyclic total dominating sets in cubic graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Edge domination on bipartite permutation graphs and cotriangulated graphs
• Bipartite permutation graphs
• Solving the weighted efficient edge domination problem on bipartite permutation graphs
• Weighted efficient domination problem on some perfect graphs
• An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs
• Acyclic domination