Linear-time algorithms for counting independent sets in bipartite permutation graphs

DOI10.1016/j.ipl.2017.02.002zbMath1422.05097OpenAlexW2587431574MaRDI QIDQ1675914

Chien-Min Chen, Min-Sheng Lin

Publication date: 3 November 2017

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2017.02.002

zbMATH Keywords

algorithmsindependent setsmaximal independent setsindependent perfect dominating setsbipartite permutation graphs

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (3)

Labelled well-quasi-order for permutation classes ⋮ Counting independent sets in cocomparability graphs ⋮ Computing the numbers of independent sets and matchings of all sizes for graphs with bounded treewidth

Cites Work

• Unnamed Item
• Counting independent sets in a tolerance graph
• Edge domination on bipartite permutation graphs and cotriangulated graphs
• Visibility graphs of towers
• Counting independent sets in tree convex bipartite graphs
• Fast and simple algorithms to count the number of vertex covers in an interval graph
• Counting the number of independent sets in chordal graphs
• Bandwidth of bipartite permutation graphs in polynomial time
• Bipartite permutation graphs
• Solving the weighted efficient edge domination problem on bipartite permutation graphs
• Linear structure of bipartite permutation graphs and the longest path problem
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• The Complexity of Enumeration and Reliability Problems

This page was built for publication: Linear-time algorithms for counting independent sets in bipartite permutation graphs