Some Efficient Algorithms for Permutation Graphs

DOI10.1006/jagm.1994.1021zbMath0804.68102OpenAlexW2012809896MaRDI QIDQ4290917

Qi Zheng, Oscar H. Ibarra

Publication date: 5 May 1994

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jagm.1994.1021

zbMATH Keywords

connected dominating setpermutation graphsminimum Steiner setsingle-source shortest path

Mathematics Subject Classification ID

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

Related Items

Connected domination and dominating clique in trapezoid graphs ⋮ A polynomial-time algorithm for the paired-domination problem on permutation graphs ⋮ An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs ⋮ Dominating the complements of bounded tolerance graphs and the complements of trapezoid graphs