Are unique subgraphs not easier to find?

DOI10.1016/j.ipl.2018.02.010zbMath1476.68211OpenAlexW2790074285MaRDI QIDQ1707980

Andrzej Lingas, Mirosław Kowaluk

Publication date: 4 April 2018

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2018.02.010

zbMATH Keywords

time 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) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• Fast rectangular matrix multiplication and applications
• Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
• Unique Maximum Matching Algorithms
• Unique subgraphs are not easier to find
• 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
• Finding Four-Node Subgraphs in Triangle Time
• Experimental and Efficient Algorithms

This page was built for publication: Are unique subgraphs not easier to find?