Enumerating simple paths from connected induced subgraphs

DOI10.1007/s00373-018-1966-9zbMath1402.05104arXiv1606.00289OpenAlexW2416774730WikidataQ129027922 ScholiaQ129027922MaRDI QIDQ1756087

Pierre-Louis Giscard, Paul Rochet

Publication date: 11 January 2019

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1606.00289

zbMATH Keywords

self-avoiding walksdirected graphHamiltonian pathsdominating setsinclusion-exclusionsimple cycles

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Paths and cycles (05C38) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40)

Related Items (1)

A general purpose algorithm for counting simple cycles and simple paths of any length

Cites Work

• Unnamed Item
• Unnamed Item
• Complexity of counting cycles using zeons
• A finite-difference sieve to count paths and cycles by length
• Finding and counting given length cycles
• Inclusion and exclusion algorithm for the Hamiltonian path problem
• The self-avoiding walk.
• The number of \(n\)-cycles in a graph
• Dynamic programming meets the principle of inclusion and exclusion
• Algorithms to count paths and cycles
• On the determination of redundancies in sociometric chains
• The traveling salesman problem in bounded degree graphs
• Counting Paths and Packings in Halves

This page was built for publication: Enumerating simple paths from connected induced subgraphs