Finding a minimum independent dominating set in a permutation graph

DOI10.1016/0166-218X(88)90064-9zbMath0667.05055MaRDI QIDQ1117255

Glenn K. Manacher, Mikhail J. Atallah, Jorge Urrutia

Publication date: 1988

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

permutation graphminimum independent dominating set

Mathematics Subject Classification ID

Graph theory (05C99)

Related Items

Coloring permutation graphs in parallel, A theorem on permutation graphs with applications, Fast algorithms for the dominating set problem on permutation graphs, On-line algorithms for the dominating set problem, On the feedback vertex set problem in permutation graphs, An efficient algorithm to solve the distancek-domination problem on permutation graphs, An efficient algorithm for maxdominance, with applications, Generate all maximal independent sets in permutation graphs, The weighted maximum independent set problem in permutation graphs, The complexity of domination problems in circle graphs, A tight bound on the number of mobile servers to guarantee transferability among dominating configurations, A new approach for the domination problem on permutation graphs, Bibliography on domination in graphs and some basic definitions of domination parameters

Cites Work

• Unnamed Item
• An efficient algorithm for maxdominance, with applications
• Some beautiful arguments using mathematical induction
• Maintenance of configurations in the plane
• Some modified algorithms for Dijkstra's longest upsequence problem
• Domination in permutation graphs