Linear-time algorithm for the paired-domination problem in convex bipartite graphs
From MaRDI portal
Publication:692884
DOI10.1007/S00224-011-9378-8zbMATH Open1253.68175OpenAlexW2026285219MaRDI QIDQ692884FDOQ692884
Authors: Ruo-Wei Hung 
Publication date: 6 December 2012
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-011-9378-8
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
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)
Cites Work
- Introduction to algorithms.
- Title not available (Why is that?)
- Title not available (Why is that?)
- Graph Classes: A Survey
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Minimum feedback vertex sets in cocomparability graphs and complex bipartite graphs
- Matchings in node-weighted convex bipartite graphs
- Linear algorithm for optimal path cover problem on interval graphs
- HAMILTONian circuits in chordal bipartite graphs
- Paired-domination in graphs
- Domination in convex and chordal bipartite graphs
- Maximum matching in a convex bipartite graph
- Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems
- A linear time algorithm for maximum matchings in convex, bipartite graphs
- Dynamic Matchings in Convex Bipartite Graphs
- Labelling algorithms for paired-domination problems in block and interval graphs
- The induced matching and chain subgraph cover problems for convex bipartite graphs
- Paired-domination of trees
- A polynomial-time algorithm for the paired-domination problem on permutation graphs
- Paired domination on interval and circular-arc graphs
- An O(n)-Time Algorithm for the Paired-Domination Problem on Permutation Graphs
- A linear-time algorithm for paired-domination problem in strongly chordal graphs
- Finding maximum edge bicliques in convex bipartite graphs
- The bottleneck independent domination on the classes of bipartite graphs and block graphs.
- A polynomial-time algorithm for the dominating induced matching problem in the class of convex graphs
- NP-completeness results for some problems on subclasses of bipartite and chordal graphs
- Deferred-query: An efficient approach for some problems on interval graphs
- Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs
- Edge domination on bipartite permutation graphs and cotriangulated graphs
- Algorithms for maximum independent set in convex bipartite graphs
- On the complexity of the k-chain subgraph cover problem
- Efficient algorithms to solve the link-orientation problem for multi-square, convex-bipartite, and convex-split networks
- An improved Boolean circuit for maximum matching in a convex bipartite graph
- An 0(n log n) algorithm for the convex bipartite matching problem
Cited In (14)
- Title not available (Why is that?)
- Circular convex bipartite graphs: feedback vertex set
- \(R\)-total domination on convex bipartite graphs
- Algorithmic aspects of upper paired-domination in graphs
- An optimal algorithm to find minimum k-hop dominating set of interval graphs
- Circular convex bipartite graphs: feedback vertex sets
- A linear-time algorithm for weighted paired-domination on block graphs
- A linear-time algorithm for paired-domination on circular-arc graphs
- Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs
- A linear time algorithm for computing a minimum paired-dominating set of a convex bipartite graph
- An O(n)-Time Algorithm for the Paired-Domination Problem on Permutation Graphs
- Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs
- A linear time algorithm for maximum matchings in convex, bipartite graphs
- An optimal algorithm to find minimum \(k\)-hop connected dominating set of permutation 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)
