Twin-width. III: Max independent set, min dominating set, and coloring
type: Item
instance of: scholarly article
title: Twin-width. III: Max independent set, min dominating set, and coloring
author: Édouard Bonnet
author: Colin Geniet
author: Eun Jung Kim
author: Stéphan Thomassé
author: Rémi Watrigant
published in: SIAM Journal on Computing
publication date: 2024-11-01T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q27
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 7937497
zbMATH Keywords: twin-width
zbMATH Keywords: max independent set
zbMATH Keywords: min dominating set
zbMATH Keywords: coloring
zbMATH Keywords: parameterized algorithms
zbMATH Keywords: approximation algorithms
MaRDI profile type: Publication
cites work: Crossing patterns of semi-algebraic sets
cites work: Approximation algorithms for NP-complete problems on planar graphs
cites work: Approximating highly inapproximable problems on graphs of bounded twin-width
cites work: On problems without polynomial kernels
cites work: Graphs of bounded cliquewidth are polynomially $χ$-bounded
cites work: Twin-width II: small classes
cites work: Twin-width and polynomial kernels
cites work: Twin-width I: Tractable FO Model Checking
cites work: Packing and covering balls in graphs excluding a minor
cites work: Filtering Search: A New Approach to Query-Answering
cites work: Q3651735
cites work: Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs
cites work: The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
cites work: Linear time solvable optimization problems on graphs of bounded clique-width
cites work: Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
cites work: Bounding the vertex cover number of a hypergraph
cites work: Analytical approach to parallel repetition
cites work: Planar Subgraph Isomorphism Revisited
cites work: Classes of graphs with small rank decompositions are \(\chi \)-bounded
cites work: Constant-factor approximation of the domination number in sparse graphs
cites work: Subgraph Isomorphism in Planar Graphs and Related Problems
cites work: Diameter and treewidth in minor-closed graph families
cites work: Fixed-parameter tractability, definability, and model-checking
cites work: Infeasibility of instance compression and succinct PCPs for NP
cites work: The complexity of first-order and monadic second-order logic revisited
cites work: A linear-time algorithm for a special case of disjoint set union
cites work: The ellipsoid method and its consequences in combinatorial optimization
cites work: Polynomial-time algorithm for Maximum Weight Independent Set on P6-free graphs
cites work: Finding small patterns in permutations in linear time
cites work: \(\epsilon\)-nets and simplex range queries
cites work: On the complexity of \(k\)-SAT
cites work: Which problems have strongly exponential complexity?
cites work: Approximation algorithms for combinatorial problems
cites work: Q5874311
cites work: On the ratio of optimal integral and fractional covers
cites work: Polynomial bounds for centered colorings on proper minor-closed graph classes
cites work: Q4770411
cites work: Interval Stabbing Problems in Small Integer Ranges
cites work: Positive-instance driven dynamic programming for treewidth
cites work: Q4633908
DOI: 10.1137/21M142188X
description: scientific article; zbMATH DE number 7937497