Counting Homomorphic Cycles in Degenerate Graphs

DOI10.1145/3560820arXiv2011.05957OpenAlexW3104978401WikidataQ123328815 ScholiaQ123328815MaRDI QIDQ6051927

Raphael Yuster, Yevgeny Levanzov, Asaf Shapira, Lior Gishboliner

Publication date: 23 October 2023

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

degeneracysubgraph countingcycle detectioncycle homomorphisms

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

• Sparsity. Graphs, structures, and algorithms
• Finding and counting given length cycles
• The complexity of counting homomorphisms seen from the other side
• The challenges of unbounded treewidth in parameterised subgraph counting problems
• Efficient algorithms for clique problems
• Detecting directed 4-cycles still faster
• Fast rectangular matrix multiplication and applications
• Faster algorithms for counting subgraphs in sparse graphs
• Emergence of Scaling in Random Networks
• Powers of tensors and fast matrix multiplication
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• Arboricity and Subgraph Listing Algorithms
• Smallest-last ordering and clustering and graph coloring algorithms
• Finding a Minimum Circuit in a Graph
• Finding Even Cycles Even Faster
• Color-coding
• The Parameterized Complexity of Counting Problems
• Homomorphisms are a good basis for counting small subgraphs
• Finding, minimizing, and counting weighted subgraphs
• Graph pattern detection: hardness for all induced patterns and faster non-induced cycles
• Multiplying matrices faster than coppersmith-winograd
• On generalized graphs
• Counting Subgraphs in Degenerate Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Counting Homomorphic Cycles in Degenerate Graphs