@inproceedings{62b7bdb329254289847deba2854ac1e6,
title = "Fixed-parameter complexity of minimum profile problems",
abstract = "An ordering of a graph G = (V, E] is a one-to-one mapping α : V → \{1,2,..., |V|\}. The profile of an ordering α of G is prf α(G) = σvεV(α(u) - min\{α(u) : u ∈ N[v\}\}); here N[v] denotes the closed neighborhood of v. The profile prf(G) of G is the minimum of prfα(G) over all orderings α of G. It is well-known that prf(G) equals the minimum number of edges in an interval graph H that contains G as a subgraph. We show by reduction to a problem kernel of linear size that deciding whether the profile of a connected graph G = (V, E) is at most |V| -1 + k is fixed-parameter tractable with respect to the parameter k. Since |V| -1 is a tight lower bound for the profile of a connected graph G = (V,E), the parameterization above the guaranteed value |V| -1 is of particular interest.",
author = "Gregory Gutin and Stefan Szeider and Anders Yeo",
year = "2006",
doi = "10.1007/11847250\_6",
language = "English",
isbn = "3540390987",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "60--71",
booktitle = "Parameterized and Exact Computation - Second International Workshop, IWPEC 2006, Proceedings",
address = "Germany",
note = "2nd International Workshop on Parameterized and Exact Computation, IWPEC 2006 ; Conference date: 13-09-2006 Through 15-09-2006",
}