The complexity of domination problems in circle graphs

DOI10.1016/0166-218X(93)90178-QzbMath0786.05079WikidataQ56503307 ScholiaQ56503307MaRDI QIDQ1209148

J. Mark Keil

Publication date: 16 May 1993

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

zbMATH Keywords

complexitypolynomial time algorithmdominating setNP-completedominationcircle graphsdominating clique

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (34)

Strong edge coloring of circle graphs ⋮ Semitotal domination on AT-free graphs and circle graphs ⋮ Algorithmic results in secure total dominating sets on graphs ⋮ TS-reconfiguration of dominating sets in circle and circular-arc graphs ⋮ Subtree filament graphs are subtree overlap graphs ⋮ Graph classes with structured neighborhoods and algorithmic applications ⋮ Complexity-separating graph classes for vertex, edge and total colouring ⋮ Algorithmic Aspects of Disjunctive Total Domination in Graphs ⋮ Algorithmic results on locating-total domination in graphs ⋮ Algorithmic results in Roman dominating functions on graphs ⋮ Algorithmic and complexity aspects of problems related to total restrained domination for graphs ⋮ Parameterized domination in circle graphs ⋮ Domination and total domination on asteroidal triple-free graphs ⋮ On total \(f\)-domination: polyhedral and algorithmic results ⋮ Independence and domination in polygon graphs ⋮ Paired-domination problem on distance-hereditary graphs ⋮ Approximating the minimum clique cover and other hard problems in subtree filament graphs ⋮ Dominating sets reconfiguration under token sliding ⋮ A survey of selected recent results on total domination in graphs ⋮ Algorithmic results on double Roman domination in graphs ⋮ Unnamed Item ⋮ Connected Domination ⋮ Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width ⋮ Linear separation of connected dominating sets in graphs ⋮ An output sensitive algorithm for computing a maximum independent set of a circle graph ⋮ Graph Classes with Structured Neighborhoods and Algorithmic Applications ⋮ Maximum Independent Set in 2-Direction Outersegment Graphs ⋮ Defensive alliances in graphs ⋮ APX-hardness of domination problems in circle graphs ⋮ Revising Johnson's table for the 21st century ⋮ Algorithmic aspects of k-part degree restricted domination in graphs ⋮ Offensive alliances in graphs ⋮ A linear time algorithm to compute a minimum restrained dominating set in proper interval graphs ⋮ On connected dominating sets of restricted diameter

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Clustering and domination in perfect graphs
• On domination problems for permutation and other graphs
• Finding a minimum independent dominating set in a permutation graph
• Independent domination in chordal graphs
• Dominating sets in perfect graphs
• Permutation graphs: Connected domination and Steiner trees
• Domination on Cocomparability Graphs
• On the Algorithmic Complexity of Total Domination
• Domination in permutation graphs
• On the Complexity of Nonconvex Covering
• The NP-completeness column: an ongoing guide
• A Dynamic Programming Approach to the Dominating Set Problem on k-Trees
• Dominating Sets in Chordal Graphs
• Recognizing circle graphs in polynomial time
• Algorithms for a maximum clique and a maximum independent set of a circle graph

This page was built for publication: The complexity of domination problems in circle graphs