Unique subgraphs are not easier to find

DOI10.1080/00207160.2012.701287zbMATH Open1310.68113OpenAlexW2172178506MaRDI QIDQ2855752FDOQ2855752

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

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

Recommendations

• Unique small subgraphs are not easier to find
• Are unique subgraphs not easier to find?
• On the number of unique subgraphs of a graph
• Induced subgraph isomorphism: are some patterns substantially easier than others?
• Induced subgraph isomorphism: are some patterns substantially easier than others?

zbMATH Keywords

graph algorithmssubgraph isomorphismtime complexityinduced subgraph isomorphismunique subgraph occurrence

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (2)

• On the number of unique subgraphs of a graph
• Are unique subgraphs not easier to find?

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2855752)