Back to Search
Start Over
Counting independent sets in tree convex bipartite graphs
- Source :
- Discrete Applied Mathematics. 218:113-122
- Publication Year :
- 2017
- Publisher :
- Elsevier BV, 2017.
-
Abstract
- The problems of counting independent sets, maximal independent sets, and independent perfect dominating sets are #P-complete for bipartite graphs, but can be solved in polynomial time for convex bipartite graphs, which are a subclass of bipartite graphs This paper studies these problems for tree convex bipartite graphs, which are a class of graphs between bipartite graphs and convex bipartite graphs. A bipartite graph G with bipartition (XY) is called tree convex, if a tree T defined on X exists, such that for every vertex y in Y, the neighbors of y form a subtree of T If the associated tree T is simply a path, then G is just a convex bipartite graph. This paper first proves that the problems of counting independent sets, maximal independent sets, and independent perfect dominating sets remain #P-complete for tree convex bipartite graphs even when the associated tree T is only a comb or a star. This paper then presents polynomial-time algorithms to solve these problems for tree convex bipartite graphs when the associated tree T is restricted to a triad, which consists of three paths with one common endpoint.
- Subjects :
- Discrete mathematics
Mathematics::Combinatorics
Applied Mathematics
010102 general mathematics
Convex bipartite graph
0102 computer and information sciences
Tree-depth
01 natural sciences
Complete bipartite graph
Combinatorics
Computer Science::Discrete Mathematics
010201 computation theory & mathematics
Chordal graph
TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY
Independent set
Bipartite graph
Discrete Mathematics and Combinatorics
Cograph
Maximal independent set
0101 mathematics
MathematicsofComputing_DISCRETEMATHEMATICS
Mathematics
Subjects
Details
- ISSN :
- 0166218X
- Volume :
- 218
- Database :
- OpenAIRE
- Journal :
- Discrete Applied Mathematics
- Accession number :
- edsair.doi...........eeaaf90bcf5980824b3753a543a840d4