GlobalView

Showing items 1 - 15 of 32.

Add to Quick Collection   All 32 Results

Sort:
 Add All Items to Quick Collection
Date: 2011
Language: eng
Resource Type: journal article
Identifier: http://hdl.handle.net/1959.13/936218
Description: The Convex Recoloring (CR) problem measures how far a tree of characters differs from exhibiting a so-called “perfect phylogeny”. For an input consisting of a vertex-colored tree T, the problem is to ... More
Reviewed: Reviewed
Date: 2011
Language: eng
Resource Type: journal article
Identifier: http://hdl.handle.net/1959.13/1056843
Description: We study the problem of finding occurrences of motifs in vertex-colored graphs, where a motif is a multiset of colors, and an occurrence of a motif is a subset of connected vertices whose multiset of ... More
Reviewed: Reviewed
Date: 2010
Language: eng
Resource Type: journal article
Identifier: http://hdl.handle.net/1959.13/921871
Description: The CORRELATION CLUSTERING problem, also known as the CLUSTER EDITING problem, seeks to edit a given graph by adding and deleting edges to obtain a collection of vertex-disjoint cliques, such that the... More
Reviewed: Reviewed
Date: 2010
Language: eng
Resource Type: journal article
Identifier: http://hdl.handle.net/1959.13/923287
Description: We study the parameterized complexity of several minimum label graph problems, in which we are given an undirected graph whose edges are labeled, and a property Π, and we are asked to find a subset of... More
Reviewed: Reviewed
Date: 2009
Resource Type: conference paper
Identifier: uon:8859
Description: We investigate the computational complexity of a general "compression task" centrally occurring in the recently developed technique of iterative compression for exactly solving NP-hard minimization pr... More
Reviewed: Reviewed
Date: 2009
Resource Type: journal article
Identifier: uon:6974
Description: Clique-width is a graph parameter that measures in a certain sense the complexity of a graph. Hard graph problems (e.g., problems expressible in monadic second-order logic with second-order quantifica... More
Reviewed: Reviewed
Date: 2009
Resource Type: journal article
Identifier: uon:7231
Description: In this paper, we investigate algorithms for some related graph parameters. Each of these asks for a linear ordering of the vertices of the graph (or can be formulated as such), and constructive linea... More
Reviewed: Reviewed
Date: 2009
Language: eng
Resource Type: conference paper
Identifier: http://hdl.handle.net/1959.13/919431
Description: We study low-distortion embedding of metric spaces into the line, and more generally, into the shortest path metric of trees, from the parameterized complexity perspective. Let M = M(G) be the shortes... More
Reviewed: Reviewed
Date: 2009
Language: eng
Resource Type: journal article
Identifier: http://hdl.handle.net/1959.13/808425
Description: The computation of Kemeny rankings is central to many applications in the context of rank aggregation. Given a set of permutations (votes) over a set of candidates, one searches for a “consensus permu... More
Reviewed: Reviewed
Date: 2009
Language: eng
Resource Type: conference paper
Identifier: http://hdl.handle.net/1959.13/919432
Description: We introduce overlap cluster graph modification problems where, other than in most previous work, the clusters of the target graph may overlap. More precisely, the studied graph problems ask for a min... More
Reviewed: Reviewed
Date: 2009
Resource Type: conference paper
Identifier: uon:8866
Description: The haplotype inference problem (HIP) asks to find a set of haplotypes which resolve a given set of genotypes. This problem is of enormous importance in many practical fields, such as the investigatio... More
Reviewed: Reviewed
Date: 2009
Resource Type: journal article
Identifier: uon:7412
Description: Kernelization is a strong and widely-applied technique in parameterized complexity. A kernelization algorithm, or simply a kernel, is a polynomial-time transformation that transforms any given paramet... More
Reviewed: Reviewed
Date: 2009
Language: eng
Resource Type: journal article
Identifier: http://hdl.handle.net/1959.13/809074
Description: Multiple-interval graphs are a natural generalization of interval graphs where each vertex may have more than one interval associated with it. Many applications of interval graphs also generalize to m... More
Reviewed: Reviewed
Date: 2009
Language: eng
Resource Type: conference paper
Identifier: http://hdl.handle.net/1959.13/919408
Description: The NP-complete geometric covering problem rectangle stabbing is defined as follows: Given a set of horizontal and vertical lines in the plane, a set of rectangles in the plane, and a positive integer... More
Reviewed: Reviewed
Date: 2009
Resource Type: conference paper
Identifier: uon:8865
Description: We show that three subclasses of bounded treewidth graphs are well-quasi-ordered by refinements of the minor order. Specifically, we prove that graphs with bounded feedback-vertex-set are well-quasi-o... More
Reviewed: Reviewed