Fixed-parameter complexity of minimum profile problems

DOI10.1007/S00453-007-9144-0MaRDI QIDQ958202zbMATH OpenOpenAlexFDO

Authors G. Gutin, Stefan Szeider, A. Yeo

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

above guaranteed valuefixed parameter tractabilitygraph profilekernel

Mathematics Subject Classification ID

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

Recommendations

• Fixed-Parameter Complexity of Minimum Profile Problems
• Interval Completion Is Fixed Parameter Tractable
• Characterizing Minimal Interval Completions
• Profile minimization on compositions of graphs
• The Profile Minimization Problem in Trees

Cites work

• \(E_{11}\) and M theory
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Graph searching and interval completion
• scientific article; zbMATH DE number 5605062 (Why is no real title available?)
• scientific article; zbMATH DE number 5485472 (Why is no real title available?)
• scientific article; zbMATH DE number 177539 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Incidence matrices, interval graphs and seriation in archeology
• Mapping the genome
• On interval graphs and matrice profiles
• Profile minimization problem for matrices and graphs
• Representation of a finite graph by a set of intervals on the real line
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The linear arrangement problem parameterized above guaranteed value

Cited in

(11)

• Minimum leaf out-branching and related problems
• Note on maximal bisection above tight lower bound
• Betweenness parameterized above tight lower bound
• Parameterized and approximation algorithms for the load coloring problem
• Profile minimization on products of graphs
• Fixed-Parameter Complexity of Minimum Profile Problems
• A probabilistic approach to problems parameterized above or below tight bounds
• 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
• Note on Max Lin-2 above average

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q958202)