Finding a Minimal Tree Pattern Under Neighborhood Constraints
Summary: Find minimal tree patterns conforming to schemas mapping each label to allowed neighbor bags; NP-hard but FPT parameterized by label-set size. Treats two schema languages: pairwise mutual exclusions (W[1]-hard, FPT for circular-arc graphs) and regular-expression schemas (FPT). (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
Incoming Citations (Sorted by Pagerank)
Showing 1 of 1 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 4,838 | Finding Patterns in a Knowledge Base using Keywords to Compose Table Answers | 2014 | VLDB | 5.883146e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 9 of 9 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 53 | DISCOVER: Keyword Search in Relational Databases | 2002 | VLDB | 0.00065993143 |
| 547 | Schema-Free XQuery | 2004 | VLDB | 0.00020372992 |
| 1,072 | Finding and Approximating Top-k Answers in Keyword Proximity Search | 2006 | PODS | 0.00014256848 |
| 1,453 | Keyword Proximity Search in Complex Data Graphs | 2008 | SIGMOD | 0.00011921738 |
| 1,564 | Keyword Search in Databases: The Power of RDBMS | 2009 | SIGMOD | 0.00011340407 |
| 3,116 | Learning to Create Data-Integrating Queries | 2008 | VLDB | 7.5404022e-05 |
| 9,366 | IQ: The Case for Iterative Querying for Knowledge | 2011 | CIDR | 4.3467888e-05 |
| 12,247 | Exploratory Keyword Search on Data Graphs | 2010 | SIGMOD | 4.1905499e-05 |
| 12,326 | ExQueX: Exploring and Querying XML Documents | 2009 | SIGMOD | 4.1905499e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 2,957 | Efficient Algorithms for Minimizing Tree Pattern Queries | 2002 | SIGMOD | 7.8143379e-05 |
| 11,907 | Defining Relations on Graphs: How Hard is it in the Presence of Node Partitions? | 2015 | PODS | 4.1905499e-05 |
| 12,440 | The Complexity of Reasoning about Pattern-based XML Schemas | 2007 | PODS | 4.1905499e-05 |
| 7,588 | Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data | 2012 | VLDB | 4.6996269e-05 |
| 1,236 | Minimization of Tree Pattern Queries | 2001 | SIGMOD | 0.00013107769 |
| 9,889 | The (Almost) Complete Guide to Tree Pattern Containment | 2015 | PODS | 4.2576366e-05 |
| 4,949 | Querying Graph Patterns | 2011 | PODS | 5.8090034e-05 |
| 11,835 | Minimization of Tree Pattern Queries | 2016 | PODS | 4.1905499e-05 |
| 4,019 | Efficient Evaluation and Approximation of Well-designed Pattern Trees | 2015 | PODS | 6.521716e-05 |
| 5,950 | Minimization of Tree Pattern Queries with Constraints | 2008 | SIGMOD | 5.2551296e-05 |