Betweenness parameterized above tight lower bound

2010/05/07 by Gregory Gutin, Eun Jung Kim, Matthias Mnich +1 · 2 citations
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Betweenness centrality #Centrality #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Discrete mathematics #Mathematical analysis #Mathematics #Parameterized complexity #Upper and lower bounds #graph theory and CDMA systems

paper · pdf · doi:10.1016/j.jcss.2010.05.001

openalex publication_date 2010/05/07 · crossref created 2010/05/07 · crossref issued 2010/12/01 · crossref published 2010/12/01 · crossref published-print 2010/12/01 · crossref deposited 2019/05/29 · crossref indexed 2023/01/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/02

Citations

• Invitation to Fixed-Parameter Algorithms
• Parameterized Complexity Theory
• A Geometric Approach to Betweenness
• Interval Completion Is Fixed Parameter Tractable
• Every Permutation CSP of arity 3 is Approximation Resistant
• Logarithmic Sobolev Inequalities
• Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems

Cited by

• Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems
• Betweenness problem [wikipedia]