Graph-Theoretic Concepts in Computer Science

DOI10.1007/11604686MaRDI QIDQ5897576zbMATH OpenFDO

Authors Yoshio Okamoto, Takeaki Uno, Ryuhei Uehara

Publication date 1 November 2006

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

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)

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

Cited in

(19)

• On Independent Sets and Bicliques in Graphs
• Faster exponential-time algorithms for approximately counting independent sets
• scientific article; zbMATH DE number 5842466 (Why is no real title available?)
• Proximity Search for Maximal Subgraph Enumeration
• A Method for Computing the Merrifield–Simmons Index on Benzenoid Systems
• Counting maximal independent sets in directed path graphs
• Counting the number of independent sets in chordal graphs
• Listing Maximal Independent Sets with Minimal Space and Bounded Delay
• Enumeration and maximum number of maximal irredundant sets for chordal graphs
• Counting the maximal independent sets in power set graphs
• On listing, sampling, and counting the chordal graphs with edge constraints
• Fast and simple algorithms to count the number of vertex covers in an interval graph
• Counting the number of matchings in chordal and chordal bipartite graph classes
• Enumeration aspects of maximal cliques and bicliques
• 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
• Linear time algorithms for counting the number of minimal vertex covers with minimum/maximum size in an interval graph
• scientific article; zbMATH DE number 2080986 (Why is no real title available?)

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)