Connected domination and Steiner set on weighted permutation graphs

DOI10.1016/0020-0190(92)90183-VzbMath0754.68060OpenAlexW2057476713WikidataQ126388057 ScholiaQ126388057MaRDI QIDQ1190520

C. Pandu Regan, K. Arvind

Publication date: 26 September 1992

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

Full work available at URL: https://doi.org/10.1016/0020-0190(92)90183-v

zbMATH Keywords

Steiner setpermutation graphsconnected domination\(NP\)-complete problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items

On the feedback vertex set problem in permutation graphs, Connected domination and steiner set on asteroidal triple-free graphs, The balanced connected subgraph problem for geometric intersection graphs, The \(k\)-hop connected dominating set problem: approximation and hardness, A polynomial-time algorithm for the paired-domination problem on permutation graphs, Optimal Sequential And Parallel Algorithms To Compute A Steiner Tree On Permutation Graphs, An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs

Cites Work

• Unnamed Item
• Unnamed Item
• On the domatic number of interval graphs
• Permutation graphs: Connected domination and Steiner trees
• Steiner trees, connected domination and strongly chordal graphs
• Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
• Total Domination and Irredundance in Weighted Interval Graphs
• Incremental modular decomposition
• Fibonacci heaps and their uses in improved network optimization algorithms