Parameterized complexity results for general factors in bipartite graphs with an application to constraint programming

DOI10.1007/s00453-011-9548-8zbMath1253.68151arXiv1106.3527OpenAlexW2024429727MaRDI QIDQ1759676

Gregory Gutin, Stefan Szeider, Anders Yeo, Arezou Soleimanfallah, Eun Jung Kim

Publication date: 21 November 2012

Published in: Algorithmica, Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1106.3527

zbMATH Keywords

global constraintfixed-parameter tractablegeneral factor

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Uses Software

• HIBISCUS

Cites Work

• Unnamed Item
• Unnamed Item
• Editing graphs to satisfy degree constraints: a parameterized approach
• General factors of graphs
• On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
• Parametrized complexity theory.
• Revisiting the Sequence Constraint
• Monadic Second Order Logic on Graphs with Local Cardinality Constraints
• The factorization of graphs. II
• Principles and Practice of Constraint Programming – CP 2004
• Principles and Practice of Constraint Programming – CP 2004

This page was built for publication: Parameterized complexity results for general factors in bipartite graphs with an application to constraint programming