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)

Full work available at URL https://doi.org/10.1007/11604686

zbMATH Keywords

\#P-completenessChordal graphcountingenumerationindependent setNP-completenesspolynomial time algorithm

Mathematics Subject Classification ID

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

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)

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

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)