Independent domination on tree convex bipartite graphs

DOI10.1007/978-3-642-29700-7_12MaRDI QIDQ2897988zbMATH OpenOpenAlexFDO

Authors Tian Liu, Ke Xu, Yu Song

Publication date 16 July 2012

Published in Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-29700-7_12

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• Independent Domination: Reductions from Circular- and Triad-Convex Bipartite Graphs to Convex Bipartite Graphs
• Domination in convex and chordal bipartite graphs
• Counting independent sets in tree convex bipartite graphs
• Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs
• Tree Convex Bipartite Graphs: $\mathcal{NP}$ -Complete Domination, Hamiltonicity and Treewidth

Cited in

(26)

• The bottleneck independent domination on the classes of bipartite graphs and block graphs.
• Solving problems on generalized convex graphs via mim-width
• Induced Matching in Some Subclasses of Bipartite Graphs
• Circular convex bipartite graphs: feedback vertex set
• Domination in some subclasses of bipartite graphs
• Counting independent sets and maximal independent sets in some subclasses of bipartite graphs
• Linear algorithms for red and blue domination in convex bipartite graphs
• Maximum Edge Bicliques in Tree Convex Bipartite Graphs
• Circular convex bipartite graphs: feedback vertex sets
• Feedback vertex sets on restricted bipartite graphs
• Counting independent sets in tree convex bipartite graphs
• Independent Domination: Reductions from Circular- and Triad-Convex Bipartite Graphs to Convex Bipartite Graphs
• scientific article; zbMATH DE number 6694457 (Why is no real title available?)
• Complexity of most vital nodes for independent set in graphs related to tree structures
• Solving problems on generalized convex graphs via mim-width
• Maximum weight induced matching in some subclasses of bipartite graphs
• Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs
• Dynamic matchings in left vertex weighted convex bipartite graphs
• Some new algorithmic results on co-secure domination in graphs
• Tree Convex Bipartite Graphs: $\mathcal{NP}$ -Complete Domination, Hamiltonicity and Treewidth
• Independent dominating set problem revisited
• Counting dominating sets in some subclasses of bipartite graphs
• Dominating induced matching in some subclasses of bipartite graphs
• Union closed tree convex sets
• Approximation hardness of domination problems on generalized convex graphs
• Tractable connected domination for restricted bipartite graphs

This page was built for publication: Independent domination on tree convex bipartite graphs

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