Edge domination on bipartite permutation graphs and cotriangulated graphs

DOI10.1016/0020-0190(95)94093-8MaRDI QIDQ672265zbMATHOpenAlexFDO

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

zbMATH Keywords

AlgorithmsGraph algorithmsBipartite permutation graphsEdge domination

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

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

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3674114 (Why is no real title available?)
• Bipartite permutation graphs
• Domination in convex and chordal bipartite graphs
• Edge Dominating Sets in Graphs
• Incidence matrices and interval graphs
• Minimum Edge Dominating Sets
• Permutation graphs: Connected domination and Steiner trees
• The edge domination problem

Cited in

(24)

• Approximability of the capacitated \(b\)-edge dominating set problem
• Perfect edge domination and efficient edge domination in graphs
• Grundy coloring in some subclasses of bipartite graphs and their complements
• On the algorithmic complexity of twelve covering and independence parameters of graphs
• On \(b\)-matchings and \(b\)-edge dominating sets: a 2-approximation algorithm for the 4-edge dominating set problem
• Hardness and approximation of minimum maximal matchings
• Fast and simple local algorithms for 2-edge dominating sets and 3-total vertex covers
• Minimum Maximal Matching Is NP-Hard in Regular Bipartite Graphs
• An approximation algorithm dependent on edge-coloring number for minimum maximal matching problem
• Linear time algorithms for generalized edge dominating set problems
• Decomposition algorithms for solving the minimum weight maximal matching problem
• Acyclic domination on bipartite permutation graphs
• Algorithm of acyclic dominating set problem on bipartite permutation graphs
• Integer programming formulations for the minimum weighted maximal matching problem
• Linear-time algorithms for counting independent sets in bipartite permutation graphs
• Modelling and solving the perfect edge domination problem
• Approximation hardness of edge dominating set problems
• The rook problem on saw-toothed chessboards
• Linear-time algorithm for the paired-domination problem in convex bipartite graphs
• Complexity and characterization aspects of edge-related domination for graphs
• Generalizing the induced matching by edge capacity constraints
• 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
• Maximal matching polytope in trees

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)