Fixed-parameter complexity of minimum profile problems

DOI10.1007/S00453-007-9144-0zbMath1170.68020OpenAlexW2120983666MaRDI QIDQ958202

Stefan Szeider, Anders Yeo, Gregory Gutin

Publication date: 2 December 2008

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-007-9144-0

zbMATH Keywords

fixed parameter tractabilitykernelabove guaranteed valuegraph profile

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (9)

Parameterized and approximation algorithms for the load coloring problem ⋮ Note on maximal bisection above tight lower bound ⋮ Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables ⋮ A probabilistic approach to problems parameterized above or below tight bounds ⋮ Solving MAX-\(r\)-SAT above a tight lower bound ⋮ Betweenness parameterized above tight lower bound ⋮ Note on Max Lin-2 above average ⋮ Minimum leaf out-branching and related problems ⋮ A Probabilistic Approach to Problems Parameterized above or below Tight Bounds

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Profile minimization problem for matrices and graphs
• Fixed-parameter tractability of graph modification problems for hereditary properties
• The linear arrangement problem parameterized above guaranteed value
• Incidence matrices, interval graphs and seriation in archeology
• Graph Searching and Interval Completion
• E ₁₁ and M theory
• Representation of a finite graph by a set of intervals on the real line
• On interval graphs and matrice profiles
• Mapping the genome

This page was built for publication: Fixed-parameter complexity of minimum profile problems