Parameterized complexity for iterated type partitions and modular-width

DOI10.1016/j.dam.2024.03.009MaRDI QIDQ6126724

Adele A. Rescigno, Luisa Gargano, Gennaro Cordasco

Publication date: 10 April 2024

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

fixed-parameter tractabilityparameterized complexityneighborhood diversitykernelization algorithmsmodular-width

Mathematics Subject Classification ID

Theory of computing (68Qxx) Graph theory (05Cxx) Discrete mathematics in relation to computer science (68Rxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Polynomial kernels for weighted problems
• Complexity of conflict-free colorings of graphs
• Parameterized complexity of coloring problems: treewidth versus vertex cover
• On the complexity of some colorful problems parameterized by treewidth
• Equitable colorings of bounded treewidth graphs
• An application of simultaneous diophantine approximation in combinatorial optimization
• Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity
• Algorithms parameterized by vertex cover and modular width, through potential maximal cliques
• Algorithmic meta-theorems for restrictions of treewidth
• Bin packing with fixed number of bins revisited
• Linear time solvable optimization problems on graphs of bounded clique-width
• Partitioning graphs into induced subgraphs
• Parameterized complexity of distance labeling and uniform channel assignment problems
• Faster algorithms for vertex partitioning problems parameterized by clique-width
• Integer programming in parameterized complexity: five miniatures
• Parameterized Algorithms for Modular-Width
• Cluster Vertex Deletion: A Parameterization between Vertex Cover and Clique-Width
• Integer Programming with a Fixed Number of Variables
• Intractability of Clique-Width Parameterizations
• 2-Player Nash and Nonsymmetric Bargaining Games: Algorithms and Structural Properties
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• Graph Layout Problems Parameterized by Vertex Cover
• On the Maximum Weight Clique Problem
• Total domination in graphs
• Evangelism in social networks: Algorithms and complexity
• Modular-Width: An Auxiliary Parameter for Parameterized Parallel Complexity
• Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs
• Kernelization Lower Bounds by Cross-Composition
• Iterated Type Partitions
• Target Set Selection in Dense Graph Classes
• Metric Dimension of Bounded Tree-length Graphs
• Mathematical Foundations of Computer Science 2004
• Parameterized Algorithms
• Transitiv orientierbare Graphen

This page was built for publication: Parameterized complexity for iterated type partitions and modular-width