Results 21 to 30 of about 5,303 (261)

Interval Completion Is Fixed Parameter Tractable [PDF]

open access: yesSIAM Journal on Computing, 2009
We present an algorithm with runtime $O(k^{2k}n^3m)$ for the following NP-complete problem [M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Co., San Francisco, 1979, problem GT35]: Given an arbitrary graph G on n vertices and m edges, can we obtain an interval graph by adding at most k ...
Yngve Villanger   +3 more
openaire   +2 more sources

On the Descriptive Complexity of Color Coding

open access: yesAlgorithms, 2021
Color coding is an algorithmic technique used in parameterized complexity theory to detect “small” structures inside graphs. The idea is to derandomize algorithms that first randomly color a graph and then search for an easily-detectable, small color ...
Max Bannach, Till Tantau
doaj   +1 more source

Experiments with the Fixed-Parameter Approach for Two-Layer Planarization

open access: yesJournal of Graph Algorithms and Applications, 2005
We present computational results of an implementation based on the fixed parameter tractability (FPT) approach for biplanarizing graphs. These results show that the implementation can efficiently find minimum biplanarizing sets containing up to about 18 ...
Matthew Suderman, Sue Whitesides
doaj   +1 more source

Chordal Deletion is Fixed-Parameter Tractable [PDF]

open access: yesAlgorithmica, 2006
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
openaire   +2 more sources

Vertex Cover Reconfiguration and Beyond

open access: yesAlgorithms, 2018
In the Vertex Cover Reconfiguration (VCR) problem, given a graph G, positive integers k and ℓ and two vertex covers S and T of G of size at most k, we determine whether S can be transformed into T by a sequence of at most ℓ vertex additions or removals ...
Amer E. Mouawad   +3 more
doaj   +1 more source

On 2-Clubs in Graph-Based Data Clustering: Theory and Algorithm Engineering

open access: yesJournal of Graph Algorithms and Applications, 2021
Editing a graph into a disjoint union of clusters is a standard optimization task in graph-based data clustering. Here, complementing classical work where the clusters shall be cliques, we focus on clusters that shall be 2-clubs, that is, subgraphs of ...
Aleksander Figiel   +3 more
doaj   +1 more source

Reconciling multiple genes trees via segmental duplications and losses

open access: yesAlgorithms for Molecular Biology, 2019
Reconciling gene trees with a species tree is a fundamental problem to understand the evolution of gene families. Many existing approaches reconcile each gene tree independently.
Riccardo Dondi   +2 more
doaj   +1 more source

Balanced Judicious Bipartition is Fixed-Parameter Tractable [PDF]

open access: yesSIAM Journal on Discrete Mathematics, 2019
The family of judicious partitioning problems, introduced by Bollobás and Scott to the field of extremal combinatorics, has been extensively studied from a structural point of view for over two decades. This rich realm of problems aims to counterbalance the objectives of classical partitioning problems such as Min Cut, Min Bisection, and Max Cut. While
Daniel Lokshtanov   +3 more
openaire   +8 more sources

Fixed-Parameter Tractability, Definability, and Model-Checking [PDF]

open access: yesSIAM Journal on Computing, 2001
In this article, we study parameterized complexity theory from the perspective of logic, or more specifically, descriptive complexity theory. We propose to consider parameterized model-checking problems for various fragments of first-order logic as generic parameterized problems and show how this approach can be useful in studying ...
Flum, Jörg, Grohe, Martin
openaire   +4 more sources

Spanning Trees Minimizing Branching Costs [PDF]

open access: yesDiscrete Mathematics & Theoretical Computer Science
The Minimum Branch Vertices Spanning Tree problem aims to find a spanning tree $T$ in a given graph $G$ with the fewest branch vertices, defined as vertices with a degree three or more in $T$.
Luisa Gargano, Adele A. Rescigno
doaj   +1 more source

Home - About - Disclaimer - Privacy