Edge domination on bipartite permutation graphs and cotriangulated graphs

DOI10.1016/0020-0190(95)94093-8zbMath0875.68697OpenAlexW2128024934MaRDI QIDQ672265

K. Madhukar, Maw-Shang Chang, P. Nagavamsi, Anand Srinivasan, C. Pandu Rangan

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

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

Related Items (23)

Perfect edge domination and efficient edge domination in graphs ⋮ Approximation hardness of edge dominating set problems ⋮ Acyclic domination on bipartite permutation graphs ⋮ The rook problem on saw-toothed chessboards ⋮ Hardness and approximation of minimum maximal matchings ⋮ Modelling and solving the perfect edge domination problem ⋮ Linear-time algorithms for counting independent sets in bipartite permutation graphs ⋮ Minimum Maximal Matching Is NP-Hard in Regular Bipartite 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 ⋮ Approximability of the capacitated \(b\)-edge dominating set problem ⋮ Generalizing the induced matching by edge capacity constraints ⋮ Integer programming formulations for the minimum weighted maximal matching problem ⋮ Linear-time algorithm for the paired-domination problem in convex bipartite graphs ⋮ Linear time algorithms for generalized edge dominating set problems ⋮ Complexity and characterization aspects of edge-related domination for graphs ⋮ A $(2 - c \frac{\log {n}}{n})$ Approximation Algorithm for the Minimum Maximal Matching Problem ⋮ 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 ⋮ Maximal matching polytope in trees ⋮ 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 ⋮ A 2-approximation algorithm for the minimum weight edge dominating set problem

Cites Work

• Unnamed Item
• Unnamed Item
• Domination in convex and chordal bipartite graphs
• Bipartite permutation graphs
• Permutation graphs: Connected domination and Steiner trees
• Incidence matrices and interval graphs
• Minimum Edge Dominating Sets
• Edge Dominating Sets in Graphs
• The edge domination problem

This page was built for publication: Edge domination on bipartite permutation graphs and cotriangulated graphs