Structure of squares and efficient domination in graph classes

DOI10.1016/J.TCS.2016.09.002MaRDI QIDQ338382zbMATH OpenOpenAlexFDO

Authors T. Karthick

Publication date 4 November 2016

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2016.09.002

zbMATH Keywords

graph algorithmsdominationgraph classesefficient dominationsquare graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• Efficient domination for classes of \(P_6\)-free graphs
• Hereditary efficiently dominatable graphs
• Efficient domination for some subclasses of \(P_6\)-free graphs in polynomial time
• Weighted efficient domination in two subclasses of P₆-free graphs
• New Polynomial Case for Efficient Domination in P 6-free Graphs

Cites work

• scientific article; zbMATH DE number 4085682 (Why is no real title available?)
• scientific article; zbMATH DE number 3513839 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1156657 (Why is no real title available?)
• A New Algorithm for the Maximum Weighted Stable Set Problem in Claw-Free Graphs
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
• Computing roots of graphs is hard
• Corrigendum to our paper The ellipsoid method and its consequences in combinatorial optimization
• Distance regular subgraphs of a cube
• Dominating sets in n‐cubes
• Efficient domination for classes of \(P_6\)-free graphs
• Graph Classes: A Survey
• Independence and efficient domination on \(P_6\)-free graphs
• Maximum weight independent sets in hole- and dart-free graphs
• Multiplying matrices faster than coppersmith-winograd
• New Polynomial Case for Efficient Domination in P 6-free Graphs
• New polynomial cases of the weighted efficient domination problem
• On easy and hard hereditary classes of graphs with respect to the independent set problem
• Perfect codes in the graphs \(O_k\)
• Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs
• Solving the weighted efficient edge domination problem on bipartite permutation graphs
• The weighted perfect domination problem
• The weighted perfect domination problem and its variants
• Weighted efficient domination in two subclasses of P₆-free graphs
• Weighted efficient domination problem on some perfect graphs
• Weighted independent sets in a subclass of P₆-free graphs

Cited in

(2)

• Semi square stable graphs and efficient dominating sets
• scientific article; zbMATH DE number 7597458 (Why is no real title available?)

This page was built for publication: Structure of squares and efficient domination in graph classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q338382)