Edge domination on bipartite permutation graphs and cotriangulated graphs
DOI10.1016/0020-0190(95)94093-8zbMATH Open0875.68697OpenAlexW2128024934MaRDI QIDQ672265FDOQ672265
Authors: Anand Srinivasan, K. Madhukar, P. Nagavamsi, C. Pandu Rangan, Maw-Shang Chang 
Publication date: 28 February 1997
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(95)94093-8
Recommendations
- Acyclic domination on bipartite permutation graphs
- Edge domination in complete partite graphs
- Domination in Bipartite Graphs and in Their Complements
- On edge domination numbers of graphs
- Domination in permutation graphs
- scientific article; zbMATH DE number 1896992
- Solving the weighted efficient edge domination problem on bipartite permutation graphs
- Domination in bipartite graphs
- Bounding the number of edges in permutation graphs
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- Title not available (Why is that?)
- Incidence matrices and interval graphs
- Bipartite permutation graphs
- Domination in convex and chordal bipartite graphs
- Edge Dominating Sets in Graphs
- Minimum Edge Dominating Sets
- Title not available (Why is that?)
- Permutation graphs: Connected domination and Steiner trees
- The edge domination problem
Cited In (24)
- Acyclic domination on bipartite permutation graphs
- Approximability of the capacitated \(b\)-edge dominating set problem
- The rook problem on saw-toothed chessboards
- Minimum Maximal Matching Is NP-Hard in Regular Bipartite Graphs
- A $(2 - c \frac{\log {n}}{n})$ Approximation Algorithm for the Minimum Maximal Matching Problem
- A 2-approximation algorithm for the minimum weight edge dominating set problem
- Hardness and approximation of minimum maximal matchings
- Integer programming formulations for the minimum weighted maximal matching problem
- Linear time algorithms for generalized edge dominating set problems
- Linear-time algorithm for the paired-domination problem in convex bipartite graphs
- Generalizing the induced matching by edge capacity constraints
- Fast and Simple Local Algorithms for 2-Edge Dominating Sets and 3-Total Vertex Covers
- Decomposition algorithms for solving the minimum weight maximal matching problem
- Complexity and characterization aspects of edge-related domination for graphs
- Linear-time algorithms for counting independent sets in bipartite permutation graphs
- Modelling and solving the perfect edge domination problem
- Perfect edge domination and efficient edge domination in graphs
- On the algorithmic complexity of twelve covering and independence parameters of graphs
- An approximation algorithm dependent on edge-coloring number for minimum maximal matching problem
- Grundy coloring in some subclasses of bipartite graphs and their complements
- Maximal matching polytope in trees
- Algorithm of acyclic dominating set problem on bipartite permutation graphs
- On \(b\)-matchings and \(b\)-edge dominating sets: a 2-approximation algorithm for the 4-edge dominating set problem
- Approximation hardness of edge dominating set problems
This page was built for publication: Edge domination on bipartite permutation graphs and cotriangulated graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q672265)
