Counting Subgraphs via Homomorphisms

DOI10.1007/978-3-642-02927-1_8zbMath1247.05107OpenAlexW1604283551WikidataQ60488681 ScholiaQ60488681MaRDI QIDQ5902149

Omid Amini, Saket Saurabh, Fedor V. Fomin

Publication date: 14 July 2009

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-02927-1_8

zbMATH Keywords

exact algorithmscounting subgraphsparametrized algorithmscounting perfect matchingscolor coding based algorithmscomputing chromatic polynomialcounting graph homomorphismscounting Hamiltonian cycles

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (11)

Classes of graphs embeddable in order-dependent surfaces ⋮ A global decomposition theorem for excluding immersions in graphs with no edge-cut of order three ⋮ An exponential time 2-approximation algorithm for bandwidth ⋮ Capacitated domination faster than \(O(2^n)\) ⋮ Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems ⋮ Faster algorithms for finding and counting subgraphs ⋮ New plain-exponential time classes for graph homomorphism ⋮ On the parameterized complexity of vertex cover and edge cover with connectivity constraints ⋮ Exact and approximate bandwidth ⋮ An Exponential Time 2-Approximation Algorithm for Bandwidth ⋮ Unnamed Item

This page was built for publication: Counting Subgraphs via Homomorphisms