On Independent Sets and Bicliques in Graphs

DOI10.1007/978-3-540-92248-3_16zbMath1202.05096OpenAlexW2104822344MaRDI QIDQ5302053

Serge Gaspers, Mathieu Liedloff, Dieter Kratsch

Publication date: 20 January 2009

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-92248-3_16

zbMATH Keywords

number of maximal independent setsnumber of maximal bicliques

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (14)

Counting Maximal Independent Sets in Subcubic Graphs ⋮ Unnamed Item ⋮ On vertex independence number of uniform hypergraphs ⋮ On independent sets and bicliques in graphs ⋮ Exact exponential-time algorithms for finding bicliques ⋮ Covering and packing in linear space ⋮ Bicolored independent sets and bicliques ⋮ Feedback Vertex Sets in Tournaments ⋮ Tight lower bounds on the number of bicliques in false-twin-free graphs ⋮ Tight lower bounds on the number of bicliques in false-twin-free graphs ⋮ A convexity upper bound for the number of maximal bicliques of a bipartite graph ⋮ A new decomposition technique for maximal clique enumeration for sparse graphs ⋮ Efficient enumeration of maximal induced bicliques ⋮ Enumeration aspects of maximal cliques and bicliques

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Generating bicliques of a graph in lexicographic order
• Consensus algorithms for the generation of all maximal bicliques
• On the minimum feedback vertex set problem: Exact and enumeration algorithms
• On generating all maximal independent sets
• 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
• On Bipartite and Multipartite Clique Problems
• A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances
• A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set in Graphs
• Measure and conquer
• Algorithms for maximum independent sets
• Approximating Clique and Biclique Problems
• A fast incremental algorithm for building lattices
• The Number of Maximal Independent Sets in Triangle-Free Graphs
• Algorithm Theory - SWAT 2004
• Node-and edge-deletion NP-complete problems
• Automata, Languages and Programming
• Graph-Theoretic Concepts in Computer Science
• On the generation of bicliques of a graph
• On cliques in graphs
• Bicliques in graphs. I: Bounds on their number

This page was built for publication: On Independent Sets and Bicliques in Graphs