Solving the weighted efficient edge domination problem on bipartite permutation graphs

DOI10.1016/S0166-218X(98)00057-2zbMath0911.05039OpenAlexW2093628106MaRDI QIDQ1270782

Chuan Yi Tang, Chin Lung Lu

Publication date: 23 April 1999

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

bipartite graphsNP-completeefficient edge dominationbipartite permutation graphs

Mathematics Subject Classification ID

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

Related Items (32)

Perfect edge domination and efficient edge domination in graphs ⋮ Acyclic domination on bipartite permutation graphs ⋮ Perfect edge domination: hard and solvable cases ⋮ Efficient domination through eigenvalues ⋮ Kernelization of edge perfect code and its variants ⋮ Structure of squares and efficient domination in graph classes ⋮ Finding dominating induced matchings in \(P_9\)-free graphs in polynomial time ⋮ Dominating induced matchings in \(S_{1 , 2 , 4}\)-free graphs ⋮ Modelling and solving the perfect edge domination problem ⋮ Linear-time algorithms for counting independent sets in bipartite permutation graphs ⋮ Finding dominating induced matchings in \(S_{2, 2, 3}\)-free graphs in polynomial time ⋮ Critical properties of bipartite permutation graphs ⋮ Finding dominating induced matchings in \(P_{10}\)-free graphs in polynomial time ⋮ Weighted efficient domination in two subclasses of \(P_6\)-free graphs ⋮ A note on efficient domination in a superclass of \(P_5\)-free graphs ⋮ Dominating induced matchings in graphs without a skew star ⋮ Exact algorithms for minimum weighted dominating induced matching ⋮ Finding dominating induced matchings in \(P_8\)-free graphs in polynomial time ⋮ Fast algorithms for some dominating induced matching problems ⋮ On the complexity of the dominating induced matching problem in hereditary classes of graphs ⋮ Efficient domination for classes of \(P_6\)-free graphs ⋮ Dominating induced matching in some subclasses of bipartite graphs ⋮ Efficient edge domination in regular graphs ⋮ Weighted efficient domination for some classes of \(H\)-free and of \((H_1, H_2)\)-free graphs ⋮ On efficient domination for some classes of \(H\)-free chordal graphs ⋮ Labeling bipartite permutation graphs with a condition at distance two ⋮ The Maximum Number of Dominating Induced Matchings ⋮ A Polynomial-time Algorithm for the Dominating Induced Matching Problem in the Class of Convex Graphs ⋮ Dominating Induced Matchings ⋮ Finding dominating induced matchings in \(S_{1, 1, 5}\)-free graphs in polynomial time ⋮ On efficient domination for some classes of \(H\)-free bipartite graphs ⋮ Exact algorithms for dominating induced matching based on graph partition

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The weighted perfect domination problem
• Bipartite permutation graphs
• Efficient edge domination problems in graphs
• Polynomial algorithms for the weighted perfect domination problems on chordal graphs and split graphs
• A linear time algorithm to solve the weighted perfect domination problem in series-parallel graphs
• Weighted independent perfect domination on cocomparability graphs
• The weighted perfect domination problem and its variants
• THE PARALLEL ALGORITHMS FOR DETERMINING EDGE-PACKING AND EFFICIENT EDGE DOMINATING SETS IN INTERVAL GRAPHS

This page was built for publication: Solving the weighted efficient edge domination problem on bipartite permutation graphs