Linear-time algorithm for the paired-domination problem in convex bipartite graphs
From MaRDI portal
Publication:692884
DOI10.1007/s00224-011-9378-8zbMath1253.68175MaRDI 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
graph algorithms; linear-time algorithms; total domination; paired-domination; convex bipartite graphs
68Q25: Analysis of algorithms and problem complexity
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Related Items
An optimal algorithm to find minimum k-hop dominating set of interval graphs, Circular convex bipartite graphs: feedback vertex sets, Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs, Algorithmic aspects of upper paired-domination in graphs, A linear-time algorithm for paired-domination on circular-arc graphs, Circular Convex Bipartite Graphs: Feedback Vertex Set
Cites Work
- Unnamed Item
- Unnamed Item
- 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
- Maximum matching in a convex bipartite graph
