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.8887949e-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 |
|---|---|---|---|---|
| 54 | DISCOVER: Keyword Search in Relational Databases | 2002 | VLDB | 0.00066047203 |
| 548 | Schema-Free XQuery | 2004 | VLDB | 0.00020391259 |
| 1,073 | Finding and Approximating Top-k Answers in Keyword Proximity Search | 2006 | PODS | 0.00014264992 |
| 1,453 | Keyword Proximity Search in Complex Data Graphs | 2008 | SIGMOD | 0.00011917976 |
| 1,564 | Keyword Search in Databases: The Power of RDBMS | 2009 | SIGMOD | 0.00011350495 |
| 3,110 | Learning to Create Data-Integrating Queries | 2008 | VLDB | 7.5475982e-05 |
| 9,359 | IQ: The Case for Iterative Querying for Knowledge | 2011 | CIDR | 4.3509599e-05 |
| 12,239 | Exploratory Keyword Search on Data Graphs | 2010 | SIGMOD | 4.1945683e-05 |
| 12,318 | ExQueX: Exploring and Querying XML Documents | 2009 | SIGMOD | 4.1945683e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 2,956 | Efficient Algorithms for Minimizing Tree Pattern Queries | 2002 | SIGMOD | 7.821865e-05 |
| 11,899 | Defining Relations on Graphs: How Hard is it in the Presence of Node Partitions? | 2015 | PODS | 4.1945683e-05 |
| 12,431 | The Complexity of Reasoning about Pattern-based XML Schemas | 2007 | PODS | 4.1945683e-05 |
| 7,584 | Adding Logical Operators to Tree Pattern Queries on Graph-Structured Data | 2012 | VLDB | 4.7041255e-05 |
| 1,235 | Minimization of Tree Pattern Queries | 2001 | SIGMOD | 0.00013120483 |
| 9,890 | The (Almost) Complete Guide to Tree Pattern Containment | 2015 | PODS | 4.2617199e-05 |
| 4,946 | Querying Graph Patterns | 2011 | PODS | 5.8149362e-05 |
| 11,827 | Minimization of Tree Pattern Queries | 2016 | PODS | 4.1945683e-05 |
| 4,058 | Efficient Evaluation and Approximation of Well-designed Pattern Trees | 2015 | PODS | 6.4866036e-05 |
| 5,948 | Minimization of Tree Pattern Queries with Constraints | 2008 | SIGMOD | 5.2602218e-05 |