On independent sets and bicliques in graphs
From MaRDI portal
Publication:2428684
DOI10.1007/s00453-010-9474-1zbMath1239.05101OpenAlexW2134046427MaRDI QIDQ2428684
Serge Gaspers, Dieter Kratsch, Mathieu Liedloff
Publication date: 26 April 2012
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-010-9474-1
maximal independent setsmaximal bicliquescounting algorithmscombinatorial boundexact exponential time algorithm
Extremal problems in graph theory (05C35) 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
On the number of connected sets in bounded degree graphs ⋮ The Bipartite QUBO ⋮ On finding and enumerating maximal and maximum \( k\)-partite cliques in \( k\)-partite graphs ⋮ Largest chordal and interval subgraphs faster than \(2^n\) ⋮ Colorings with few colors: counting, enumeration and combinatorial bounds ⋮ On the Number of Connected Sets in Bounded Degree Graphs ⋮ Computing Solution Space Properties of Combinatorial Optimization Problems Via Generic Tensor Networks ⋮ Computing dense and sparse subgraphs of weakly closed graphs ⋮ An exact exponential time algorithm for counting bipartite cliques ⋮ Unnamed Item ⋮ Biclique-colouring verification complexity and biclique-colouring power graphs ⋮ Efficient algorithms for clique-colouring and biclique-colouring unichord-free graphs ⋮ Inclusion/exclusion meets measure and conquer ⋮ Linear-time algorithm for generating c-isolated bicliques
Cites Work
- Generating bicliques of a graph in lexicographic order
- Consensus algorithms for the generation of all maximal bicliques
- Counting the number of independent sets in chordal graphs
- On the minimum feedback vertex set problem: Exact and enumeration algorithms
- Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs
- The maximum edge biclique problem is NP-complete
- A fast algorithm for building lattices
- Counting models for 2SAT and 3SAT formulae
- On Bipartite and Multipartite Clique Problems
- A Fine-grained Analysis of a Simple Independent Set Algorithm
- A measure & conquer approach for the analysis of exact algorithms
- A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances
- Set Partitioning via Inclusion-Exclusion
- Inclusion/Exclusion Meets Measure and Conquer
- An Exact Algorithm for the Maximum Leaf Spanning Tree Problem
- Algorithms for maximum independent sets
- Approximating Clique and Biclique Problems
- A fast incremental algorithm for building lattices
- On Independent Sets and Bicliques in Graphs
- Algorithm Theory - SWAT 2004
- Node-and edge-deletion NP-complete problems
- Algorithms for Counting 2-Sat Solutions and Colorings with Applications
- On the generation of bicliques of a graph
- On cliques in graphs
- Bicliques in graphs. I: Bounds on their number
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
