Unique subgraphs are not easier to find

DOI10.1080/00207160.2012.701287MaRDI QIDQ2855752zbMATH OpenOpenAlexFDO

Authors Mirosław Kowaluk, Eva-Marta Lundell, 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 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)

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?

Cites work

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

Cited in

(3)

• On the number of unique subgraphs of a graph
• Unique small subgraphs are not easier to find
• 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)