Unique subgraphs are not easier to find

DOI10.1080/00207160.2012.701287zbMath1310.68113OpenAlexW2172178506MaRDI QIDQ2855752

Eva-Marta Lundell, Mirosław Kowaluk, Andrzej Lingas

Publication date: 22 October 2013

Published in: International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/00207160.2012.701287

zbMATH Keywords

graph algorithmstime complexitysubgraph isomorphisminduced subgraph isomorphismunique subgraph occurrence

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (1)

Are unique subgraphs not easier to find?

Cites Work

• Finding and counting small induced subgraphs efficiently
• Finding and counting given length cycles
• On the complexity of fixed parameter clique and dominating set
• NP is as easy as detecting unique solutions
• Matching is as easy as matrix inversion
• Fast rectangular matrix multiplication and applications
• Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
• Unique Maximum Matching Algorithms
• Counting and Detecting Small Subgraphs via Equations
• Unique Lowest Common Ancestors in Dags Are Almost as Easy as Matrix Multiplication
• Arboricity and Subgraph Listing Algorithms
• Finding a Minimum Circuit in a Graph
• Color-coding
• Subgraph Isomorphism in Planar Graphs and Related Problems
• Finding, minimizing, and counting weighted subgraphs

This page was built for publication: Unique subgraphs are not easier to find