Graph-Theoretic Concepts in Computer Science

DOI10.1007/11604686zbMATH Open1171.68638MaRDI QIDQ5897576FDOQ5897576

Authors: Yoshio Okamoto, Takeaki Uno, Ryuhei Uehara 

Publication date: 1 November 2006

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Recommendations

• Counting the number of independent sets in chordal graphs
• Counting maximal independent sets in directed path graphs
• scientific article; zbMATH DE number 2188478
• Counting the maximal independent sets in power set graphs
• Counting independent sets in cocomparability graphs

zbMATH Keywords

enumerationNP-completenesscountingindependent setpolynomial time algorithmChordal graph\#P-completeness

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cited In (19)

• On Independent Sets and Bicliques in Graphs
• Linear time algorithms for counting the number of minimal vertex covers with minimum/maximum size in an interval graph
• Enumeration and maximum number of maximal irredundant sets for chordal graphs
• Counting the number of matchings in chordal and chordal bipartite graph classes
• Title not available (Why is that?)
• On listing, sampling, and counting the chordal graphs with edge constraints
• Faster exponential-time algorithms for approximately counting independent sets
• Mixing of Markov chains for independent sets on chordal graphs with bounded separators
• Enumeration and maximum number of maximal irredundant sets for chordal graphs
• On Listing, Sampling, and Counting the Chordal Graphs with Edge Constraints
• Counting the number of independent sets in chordal graphs
• A Method for Computing the Merrifield–Simmons Index on Benzenoid Systems
• Listing Maximal Independent Sets with Minimal Space and Bounded Delay
• Fast and simple algorithms to count the number of vertex covers in an interval graph
• Proximity Search for Maximal Subgraph Enumeration
• Title not available (Why is that?)
• Enumeration aspects of maximal cliques and bicliques
• Counting maximal independent sets in directed path graphs
• Counting the maximal independent sets in power set graphs

This page was built for publication: Graph-Theoretic Concepts in Computer Science

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5897576)