Linear-time algorithm for the paired-domination problem in convex bipartite graphs
From MaRDI portal
Publication:692884
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) 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
- A linear time algorithm for computing a minimum paired-dominating set of a convex bipartite graph
- A linear-time algorithm for paired-domination problem in strongly chordal graphs
- A linear time algorithm for maximum matchings in convex, bipartite graphs
- Linear-time algorithm for paired-domination on distance-hereditary graphs
- Linear algorithms for red and blue domination in convex bipartite graphs
- A linear-time algorithm for paired-domination on circular-arc graphs
- A linear-time algorithm for weighted paired-domination on block graphs
- Linear-time algorithm for the matched-domination problem in cographs
- A polynomial-time algorithm for the paired-domination problem on permutation graphs
- Algorithmic aspects of paired disjunctive domination in graphs
Cites work
- scientific article; zbMATH DE number 1095171 (Why is no real title available?)
- scientific article; zbMATH DE number 1095172 (Why is no real title available?)
- A linear time algorithm for maximum matchings in convex, bipartite graphs
- A linear-time algorithm for paired-domination problem in strongly chordal graphs
- A polynomial-time algorithm for the dominating induced matching problem in the class of convex graphs
- A polynomial-time algorithm for the paired-domination problem on permutation graphs
- Algorithms for maximum independent set in convex bipartite graphs
- An 0(n log n) algorithm for the convex bipartite matching problem
- An O(n)-Time Algorithm for the Paired-Domination Problem on Permutation Graphs
- An improved Boolean circuit for maximum matching in a convex bipartite graph
- Deferred-query: An efficient approach for some problems on interval graphs
- Domination in convex and chordal bipartite graphs
- Dynamic Matchings in Convex Bipartite Graphs
- Edge domination on bipartite permutation graphs and cotriangulated graphs
- Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems
- Efficient algorithms to solve the link-orientation problem for multi-square, convex-bipartite, and convex-split networks
- Finding maximum edge bicliques in convex bipartite graphs
- Graph Classes: A Survey
- HAMILTONian circuits in chordal bipartite graphs
- Introduction to algorithms.
- Labelling algorithms for paired-domination problems in block and interval graphs
- Linear algorithm for optimal path cover problem on interval graphs
- Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs
- Matchings in node-weighted convex bipartite graphs
- Maximum matching in a convex bipartite graph
- Minimum feedback vertex sets in cocomparability graphs and complex bipartite graphs
- NP-completeness results for some problems on subclasses of bipartite and chordal graphs
- On the complexity of the k-chain subgraph cover problem
- Paired domination on interval and circular-arc graphs
- Paired-domination in graphs
- Paired-domination of trees
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- The bottleneck independent domination on the classes of bipartite graphs and block graphs.
- The induced matching and chain subgraph cover problems for convex bipartite graphs
Cited in
(14)- Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs
- \(R\)-total domination on convex bipartite graphs
- An O(n)-Time Algorithm for the Paired-Domination Problem on Permutation Graphs
- Algorithmic aspects of upper paired-domination in graphs
- A linear time algorithm for computing a minimum paired-dominating set of a convex bipartite graph
- A linear time algorithm for maximum matchings in convex, bipartite graphs
- An optimal algorithm to find minimum k-hop dominating set of interval graphs
- A linear-time algorithm for paired-domination on circular-arc graphs
- scientific article; zbMATH DE number 6531253 (Why is no real title available?)
- Circular convex bipartite graphs: feedback vertex set
- Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs
- An optimal algorithm to find minimum \(k\)-hop connected dominating set of permutation graphs
- A linear-time algorithm for weighted paired-domination on block graphs
- Circular convex bipartite graphs: feedback vertex sets
This page was built for publication: Linear-time algorithm for the paired-domination problem in convex bipartite graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q692884)
