Linear-time algorithm for the paired-domination problem in convex bipartite graphs
From MaRDI portal
(Redirected from Publication:692884)
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)
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
- 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 improved Boolean circuit for maximum matching in a convex bipartite graph
- An O(n)-Time Algorithm for the Paired-Domination Problem on Permutation Graphs
- 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
- scientific article; zbMATH DE number 1095171 (Why is no real title available?)
- scientific article; zbMATH DE number 1095172 (Why is no real title available?)
- 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
(16)- A linear time algorithm for maximum matchings in convex, bipartite graphs
- Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs
- A linear-time algorithm for weighted paired-domination on block graphs
- Algorithmic aspects of upper paired-domination in graphs
- A linear-time algorithm for paired-domination on circular-arc graphs
- A linear time algorithm for computing a minimum paired-dominating set of a convex bipartite graph
- Circular convex bipartite graphs: feedback vertex set
- R-total domination on convex bipartite graphs
- Circular convex bipartite graphs: feedback vertex sets
- Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs
- scientific article; zbMATH DE number 6531253 (Why is no real title available?)
- An O(n)-Time Algorithm for the Paired-Domination Problem on Permutation Graphs
- An optimal algorithm to find minimum k-hop dominating set of interval graphs
- An optimal algorithm to find minimum k-hop connected dominating set of permutation graphs
- An optimal algorithm for computing minimum k-hop dominating set of permutation graphs
- Complexity results on paired domination in cubic graphs
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)
