An efficient algorithm for maxdominance, with applications

DOI10.1007/BF01553888zbMath0664.68070OpenAlexW1966224002MaRDI QIDQ1115629

Mikhail J. Atallah, S. Rao Kosaraju

Publication date: 1989

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01553888

zbMATH Keywords

computational geometrypermutation graphminimum independent dominating setlargest empty rectanglemaxdominancetree computation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Other problems of combinatorial convexity (52A37)

Related Items

Drawing graphs in two layers, On the feedback vertex set problem in permutation graphs, Finding a minimum independent dominating set in a permutation graph, An algorithm for the determination of longest increasing subsequence in a sequence, Fast sequential and parallel algorithms for finding the largest rectangle separating two sets, On the largest empty axis-parallel box amidst \(n\) points, Efficient algorithms for the minimum weighted dominating clique problem on permutation graphs, Efficient algorithms for the largest rectangle problem, Maximum \(k\)-covering of weighted transitive graphs with applications, Circular permutation graph family with applications, An efficient algorithm for computing the maximum empty rectangle in three dimensions, Improved bottleneck domination algorithms, Fast parallel algorithms for the maximum empty rectangle problem., SKEW VORONOI DIAGRAMS, Maximal Empty Boxes Amidst Random Points, A new approach for the domination problem on permutation graphs, An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs, Fully dynamic algorithms for permutation graph coloring, Bibliography on domination in graphs and some basic definitions of domination parameters

Cites Work

• Unnamed Item
• A new algorithm for the largest empty rectangle problem
• On the maximum empty rectangle problem
• A note on finding a maximum empty rectangle
• Finding a minimum independent dominating set in a permutation graph
• 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
• Computing the Largest Empty Rectangle