Linear-time algorithm for the paired-domination problem in convex bipartite graphs
From MaRDI portal
Publication:692884
DOI10.1007/s00224-011-9378-8zbMath1253.68175OpenAlexW2026285219MaRDI QIDQ692884
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
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (9)
Circular convex bipartite graphs: feedback vertex sets ⋮ Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs ⋮ A linear-time algorithm for weighted paired-domination on block graphs ⋮ An optimal algorithm to find minimum k-hop dominating set of interval graphs ⋮ Algorithmic aspects of upper paired-domination in graphs ⋮ An optimal algorithm to find minimum k-hop connected dominating set of permutation graphs ⋮ Circular Convex Bipartite Graphs: Feedback Vertex Set ⋮ A linear-time algorithm for paired-domination on circular-arc graphs ⋮ Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs
- Edge domination on bipartite permutation graphs and cotriangulated graphs
- An 0(n log n) algorithm for the convex bipartite matching problem
- Linear algorithm for optimal path cover problem on interval graphs
- Domination in convex and chordal bipartite graphs
- Labelling algorithms for paired-domination problems in block and interval graphs
- A linear-time algorithm for paired-domination problem in strongly chordal graphs
- NP-completeness results for some problems on subclasses of bipartite and chordal graphs
- The induced matching and chain subgraph cover problems for convex bipartite graphs
- A polynomial-time algorithm for the paired-domination problem on permutation graphs
- Algorithms for maximum independent set in convex bipartite graphs
- Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- On the complexity of the k-chain subgraph cover problem
- The bottleneck independent domination on the classes of bipartite graphs and block graphs.
- Paired-domination of trees
- Minimum feedback vertex sets in cocomparability graphs and complex bipartite graphs
- A linear time algorithm for maximum matchings in convex, bipartite graphs
- HAMILTONian circuits in chordal bipartite graphs
- Paired domination on interval and circular-arc graphs
- Efficient algorithms to solve the link-orientation problem for multi-square, convex-bipartite, and convex-split networks
- A Polynomial-time Algorithm for the Dominating Induced Matching Problem in the Class of Convex Graphs
- Matchings in Node-Weighted Convex Bipartite Graphs
- Dynamic Matchings in Convex Bipartite Graphs
- Finding Maximum Edge Bicliques in Convex Bipartite Graphs
- An O(n)-Time Algorithm for the Paired-Domination Problem on Permutation Graphs
- Graph Classes: A Survey
- Deferred-query: An efficient approach for some problems on interval graphs
- Paired-domination in graphs
- Maximum matching in a convex bipartite graph
This page was built for publication: Linear-time algorithm for the paired-domination problem in convex bipartite graphs
