Graph-Theoretic Concepts in Computer Science

DOI10.1007/11604686zbMath1171.68638MaRDI QIDQ5897576

Takeaki Uno, Ryuhei Uehara, Yoshio Okamoto

Publication date: 1 November 2006

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

zbMATH Keywords

enumerationpolynomial time algorithmNP-completenesscountingindependent setChordal graph\#P-completeness

Mathematics Subject Classification ID

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) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (8)

Proximity Search for Maximal Subgraph Enumeration ⋮ A Method for Computing the Merrifield–Simmons Index on Benzenoid Systems ⋮ Fast and simple algorithms to count the number of vertex covers in an interval graph ⋮ On Independent Sets and Bicliques in Graphs ⋮ Listing Maximal Independent Sets with Minimal Space and Bounded Delay ⋮ Linear time algorithms for counting the number of minimal vertex covers with minimum/maximum size in an interval graph ⋮ Mixing of Markov chains for independent sets on chordal graphs with bounded separators ⋮ Enumeration aspects of maximal cliques and bicliques

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