Betweenness parameterized above tight lower bound
type: Item
instance of: scholarly article
title: Betweenness parameterized above tight lower bound
zbMATH Open document ID: 1209.68621
author: G. Gutin
author: Eun Jung Kim
author: Matthias Mnich
author: A. Yeo
published in: Journal of Computer and System Sciences
publication date: 2010-10-07T00:00:00Z
Mathematics Subject Classification ID: 68W10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 5796737
zbMATH Keywords: betweenness
zbMATH Keywords: parameterized problems
zbMATH Keywords: fixed-parameter tractable
zbMATH Keywords: kernel
zbMATH Keywords: polynomial kernel
zbMATH Keywords: probabilistic method
MaRDI profile type: Publication
full work available at URL: j.jcss.2010.05.001
OpenAlex ID: W2023414599
Wikidata QID: Q56486201
cites work: Ordinal embeddings of minimum relaxation
cites work: Q5417644
cites work: Ordinal Embedding: Approximation Algorithms and Dimensionality Reduction
cites work: Monotone maps, sphericity and bounded second eigenvalue
cites work: On Problems without Polynomial Kernels (Extended Abstract)
cites work: Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)
cites work: A Geometric Approach to Betweenness
cites work: Note on Max Lin-2 above average
cites work: Systems of Linear Equations over $\mathbb{F}_2$ and Problems Parameterized above Average
cites work: Q4503944
cites work: Parametrized complexity theory.
cites work: `` Strong '' NP-Completeness Results
cites work: Logarithmic Sobolev Inequalities
cites work: A Probabilistic Approach to Problems Parameterized above or below Tight Bounds
cites work: The linear arrangement problem parameterized above guaranteed value
cites work: Fixed-parameter complexity of minimum profile problems
cites work: All Ternary Permutation Constraint Satisfaction Problems Parameterized above Average Have Kernels with Quadratic Numbers of Variables
cites work: Constraint Satisfaction Problems on Intervals and Lengths
cites work: Parameterizing above Guaranteed Values: MaxSat and MaxCut
cites work: Parameterizing above or below guaranteed values
cites work: Simple linear time approximation algorithm for betweenness
cites work: Q5710169
cites work: Total Ordering Problem
cites work: Interval Completion Is Fixed Parameter Tractable
DBLP publication ID: journals/jcss/GutinKMY10
DOI: 10.1016/J.JCSS.2010.05.001
description: scientific article; zbMATH DE number 5796737