Treewidth versus clique number. II: Tree-independence number (Q6144406)

scientific article; zbMATH DE number 7796423

Language	Label	Description	Also known as
English	Treewidth versus clique number. II: Tree-independence number	scientific article; zbMATH DE number 7796423

Statements

instance of

scholarly article

0 references

title

Treewidth versus clique number. II: Tree-independence number (English)

0 references

0 references

0 references

0 references

Journal of Combinatorial Theory. Series B

0 references

publication date

29 January 2024

0 references

full work available at URL

https://arxiv.org/abs/2111.04543

0 references

zbMATH Keywords

tree decomposition

0 references

independence number

0 references

tree-independence number

0 references

weighted independent set

0 references

weighted independent packing

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Q6147372

0 references

Integer Programming Formulations and Benders Decomposition for the Maximum Induced Matching Problem

0 references

Easy problems for tree-decomposable graphs

0 references

Linear time algorithms for NP-hard problems restricted to partial k- trees

0 references

Graph classes with structured neighborhoods and algorithmic applications

0 references

The $k$-separator problem: polyhedra, complexity and approximation results

0 references

Precoloring extension. I: Interval graphs

0 references

Q4288578

0 references

Q4250226

0 references

A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

0 references

A partial k-arboretum of graphs with bounded treewidth

0 references

Treewidth computations. II. Lower bounds

0 references

The Pathwidth and Treewidth of Cographs

0 references

Twin-width II: small classes

0 references

Twin-width I: Tractable FO Model Checking

0 references

Graph Classes: A Survey

0 references

Maximum weight independent set for $\ell$claw-free graphs in polynomial time

0 references

Bounding the mim‐width of hereditary graph classes

0 references

Boolean-width of graphs

0 references

Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems

0 references

A characterisation of rigid circuit graphs

0 references

Induced matchings

0 references

Independent packings in structured graphs

0 references

Coloring and Maximum Weight Independent Set of Rectangles

0 references

The weighted independent domination problem is NP-complete for chordal graphs

0 references

Kernelization of Graph Hamiltonicity: Proper $H$-Graphs

0 references

On $H$-topological intersection graphs

0 references

On $H$-topological intersection graphs

0 references

Combinatorial problems on $H$-graphs

0 references

Substitution and $\chi$-boundedness

0 references

On the Maximum Weight Independent Set Problem in Graphs without Induced Cycles of Length at Least Five

0 references

Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs

0 references

Clustering and domination in perfect graphs

0 references

On the Relationship Between Clique-Width and Treewidth

0 references

The monadic second-order logic of graphs. I: Recognizable sets of finite graphs

0 references

Linear time solvable optimization problems on graphs of bounded clique-width

0 references

Upper bounds to the clique width of graphs

0 references

Parameterized Algorithms

0 references

Clique-width for hereditary graph classes

0 references

Treewidth versus clique number in graph classes with a forbidden structure

0 references

Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure

0 references

Connected tree-width

0 references

On rigid circuit graphs

0 references

Tree-decompositions with bags of small diameter

0 references

An approximation algorithm for the tree $t$-spanner problem on unweighted graphs via generalized chordal graphs

0 references

Q3222876

0 references

Independent domination in chordal graphs

0 references

Improved Approximation Algorithms for Minimum Weight Vertex Separators

0 references

Subexponential parameterized algorithms and kernelization on almost chordal graphs

0 references

On the tractability of optimization problems on $H$-graphs

0 references

Fast FPT-approximation of branchwidth

0 references

Large Induced Subgraphs via Triangulations and CMSO

0 references

The Complexity of Coloring Circular Arcs and Chords

0 references

Finding large induced sparse subgraphs in c >t -free graphs in quasipolynomial time

0 references

The intersection graphs of subtrees in trees are exactly the chordal graphs

0 references

Algorithmic graph theory and perfect graphs

0 references

Geometric algorithms and combinatorial optimization

0 references

Polynomial-time Algorithm for Maximum Weight Independent Set on P 6 -free Graphs

0 references

Q5749319

0 references

Structural parameterizations with modulator oblivion

0 references

Mim-width. III. Graph powers and generalized distance domination problems

0 references

A width parameter useful for chordal and co-comparability graphs

0 references

Reducibility among Combinatorial Problems

0 references

Edge dominating set and colorings on graphs with fixed clique-width

0 references

Partitioning a graph into small pieces with applications to path transversal

0 references

Lower bounds on the mim-width of some graph classes

0 references

The complexity of dissociation set problems in graphs

0 references

Approximating clique-width and branch-width

0 references

Maximum weight induced matching in some subclasses of bipartite graphs

0 references

Robust algorithms for restricted domains

0 references

Graph minors. III. Planar tree-width

0 references

Graph minors. II. Algorithmic aspects of tree-width

0 references

Algorithmic Aspects of Vertex Elimination on Graphs

0 references

Q3358765

0 references

A survey of χ‐boundedness

0 references

Tree-chromatic number

0 references

Q4944975

0 references

Efficient graph representations

0 references

Q4551369

0 references

Decomposition by clique separators

0 references

Representations of chordal graphs as subtrees of a tree

0 references

Q4869540

0 references

Node-Deletion Problems on Bipartite Graphs

0 references

Q4607892

0 references

Approximate association via dissociation

0 references

Q3002782

0 references

Satgraphs and independent domination. I

0 references

Identifiers

arXiv ID

2111.04543

0 references

DOI

10.1016/j.jctb.2023.10.006

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:6144406