Betweenness parameterized above tight lower bound

DOI10.1016/j.jcss.2010.05.001zbMath1209.68621OpenAlexW2023414599WikidataQ56486201 ScholiaQ56486201MaRDI QIDQ1959433

Eun Jung Kim, Matthias Mnich, Gregory Gutin, Anders Yeo

Publication date: 7 October 2010

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2010.05.001

zbMATH Keywords

kernelbetweennessprobabilistic methodpolynomial kernelfixed-parameter tractableparameterized problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10)

Related Items

Improved Parameterized Algorithms for above Average Constraint Satisfaction, Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey, Note on maximal bisection above tight lower bound, Unnamed Item, Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables, Characterization and representation problems for intersection betweennesses, A probabilistic approach to problems parameterized above or below tight bounds, Strict betweennesses induced by posets as well as by graphs, Solving MAX-\(r\)-SAT above a tight lower bound, Lower bounds on kernelization, Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems, Unnamed Item, Large Independent Sets in Subquartic Planar Graphs, Large Independent Sets in Triangle-Free Planar Graphs, Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems, A Probabilistic Approach to Problems Parameterized above or below Tight Bounds, Parameterizations of test cover with bounded test sizes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Note on Max Lin-2 above average
• Fixed-parameter complexity of minimum profile problems
• Parameterizing above or below guaranteed values
• Simple linear time approximation algorithm for betweenness
• The linear arrangement problem parameterized above guaranteed value
• Parametrized complexity theory.
• Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)
• Monotone maps, sphericity and bounded second eigenvalue
• On Problems without Polynomial Kernels (Extended Abstract)
• Ordinal Embedding: Approximation Algorithms and Dimensionality Reduction
• Systems of Linear Equations over $\mathbb{F}_2$ and Problems Parameterized above Average
• All Ternary Permutation Constraint Satisfaction Problems Parameterized above Average Have Kernels with Quadratic Numbers of Variables
• Interval Completion Is Fixed Parameter Tractable
• A Probabilistic Approach to Problems Parameterized above or below Tight Bounds
• Logarithmic Sobolev Inequalities
• `` Strong NP-Completeness Results
• Total Ordering Problem
• A Geometric Approach to Betweenness
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Constraint Satisfaction Problems on Intervals and Lengths
• Ordinal embeddings of minimum relaxation