A width parameter useful for chordal and co-comparability graphs (Q1680525): Difference between revisions

Latest revision as of 05:41, 28 December 2024

scientific article; zbMATH DE number 6711880

A Width Parameter Useful for Chordal and Co-comparability Graphs

Language	Label	Description	Also known as
English	A width parameter useful for chordal and co-comparability graphs	scientific article; zbMATH DE number 6711880	A Width Parameter Useful for Chordal and Co-comparability Graphs

Statements

instance of

scholarly article

0 references

title

A width parameter useful for chordal and co-comparability graphs (English)

0 references

A Width Parameter Useful for Chordal and Co-comparability Graphs (English)

0 references

author

Dong Yeap Kang

0 references

O-joung Kwon

0 references

Torstein J. F. Strømme

0 references

Jan Arne Telle

0 references

published in

Theoretical Computer Science

0 references

WALCOM: Algorithms and Computation

0 references

publication date

16 November 2017

0 references

5 May 2017

0 references

full work available at URL

https://arxiv.org/abs/1606.08087

0 references

zbMATH Keywords

mim-width

0 references

sim-width

0 references

chordal graphs

0 references

co-comparability graphs

0 references

XP algorithm

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Large minors in graphs with given independence number

0 references

Graph classes and Ramsey numbers

0 references

Graph classes with structured neighborhoods and algorithmic applications

0 references

Dominating Sets in Chordal Graphs

0 references

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

0 references

On Hadwiger's Number and the Stability Number

0 references

Contraction obstructions for treewidth

0 references

Rank-width and tree-width of \(H\)-minor-free graphs

0 references

Complete Minors and Independence Number

0 references

Computational Complexity of Generalized Domination: A Complete Dichotomy for Chordal Graphs

0 references

Parameterized complexity of generalized domination problems

0 references

Weighted domination of cocomparability graphs

0 references

Q3128916

0 references

Lower bounds on the mim-width of some graph classes

0 references

Fast Parallel Algorithms for Chordal Graphs

0 references

On the density of families of sets

0 references

A combinatorial problem; stability and order for models and theories in infinitary languages

0 references

Algorithms for Vertex Partitioning Problems on Partial k-Trees

0 references

Q4288578

0 references

A partial k-arboretum of graphs with bounded treewidth

0 references

On Compiling CNFs into Structured Deterministic DNNFs

0 references

Parameterized Algorithms

0 references

On Satisfiability Problems with a Linear Structure

0 references

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

0 references

Representation of a finite graph by a set of intervals on the real line

0 references

Modular decomposition and transitive orientation

0 references

Approximating clique-width and branch-width

0 references

Solving #SAT and MAXSAT by Dynamic Programming

0 references

Call routing and the ratcatcher

0 references

Identifiers

zbMATH Open document ID

1380.05151

0 references

1485.05139

0 references

DOI

10.1007/978-3-319-53925-6_8

0 references

10.1016/J.TCS.2017.09.006

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1680525

@@ Property / DOI @@
-.1016/j.tcs.2017.09.006
@@ Property / DOI: 10.1016/j.tcs.2017.09.006 / rank @@
-Normal rank
@@ Property / DOI @@
+.1016/J.TCS.2017.09.006
@@ Property / DOI: 10.1016/J.TCS.2017.09.006 / rank @@
+Normal rank
@@ Property / cites work @@
+Large minors in graphs with given independence number
+Normal rank
@@ Property / cites work @@
+Graph classes and Ramsey numbers
@@ Property / cites work: Graph classes and Ramsey numbers / rank @@
+Normal rank
@@ Property / cites work @@
+Graph classes with structured neighborhoods and algorithmic applications
+Normal rank
@@ Property / cites work @@
+Dominating Sets in Chordal Graphs
@@ Property / cites work: Dominating Sets in Chordal Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
+Normal rank
@@ Property / cites work @@
+On Hadwiger's Number and the Stability Number
@@ Property / cites work: On Hadwiger's Number and the Stability Number / rank @@
+Normal rank
@@ Property / cites work @@
+Contraction obstructions for treewidth
@@ Property / cites work: Contraction obstructions for treewidth / rank @@
+Normal rank
@@ Property / cites work @@
+Rank-width and tree-width of \(H\)-minor-free graphs
+Normal rank
@@ Property / cites work @@
+Complete Minors and Independence Number
@@ Property / cites work: Complete Minors and Independence Number / rank @@
+Normal rank
@@ Property / cites work @@
+Computational Complexity of Generalized Domination: A Complete Dichotomy for Chordal Graphs
+Normal rank
@@ Property / cites work @@
+Parameterized complexity of generalized domination problems
+Normal rank
@@ Property / cites work @@
+Weighted domination of cocomparability graphs
@@ Property / cites work: Weighted domination of cocomparability graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Q3128916
@@ Property / cites work: Q3128916 / rank @@
+Normal rank
@@ Property / cites work @@
+Lower bounds on the mim-width of some graph classes
+Normal rank
@@ Property / cites work @@
+Fast Parallel Algorithms for Chordal Graphs
@@ Property / cites work: Fast Parallel Algorithms for Chordal Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+On the density of families of sets
@@ Property / cites work: On the density of families of sets / rank @@
+Normal rank
@@ Property / cites work @@
+A combinatorial problem; stability and order for models and theories in infinitary languages
+Normal rank
@@ Property / cites work @@
+Algorithms for Vertex Partitioning Problems on Partial k-Trees
+Normal rank
@@ Property / cites work @@
+Q4288578
@@ Property / cites work: Q4288578 / rank @@
+Normal rank
@@ Property / cites work @@
+A partial k-arboretum of graphs with bounded treewidth
+Normal rank
@@ Property / cites work @@
+On Compiling CNFs into Structured Deterministic DNNFs
+Normal rank
@@ Property / cites work @@
+Parameterized Algorithms
@@ Property / cites work: Parameterized Algorithms / rank @@
+Normal rank
@@ Property / cites work @@
+On Satisfiability Problems with a Linear Structure
+Normal rank
@@ Property / cites work @@
+The intersection graphs of subtrees in trees are exactly the chordal graphs
+Normal rank
@@ Property / cites work @@
+Representation of a finite graph by a set of intervals on the real line
+Normal rank
@@ Property / cites work @@
+Modular decomposition and transitive orientation
@@ Property / cites work: Modular decomposition and transitive orientation / rank @@
+Normal rank
@@ Property / cites work @@
+Approximating clique-width and branch-width
@@ Property / cites work: Approximating clique-width and branch-width / rank @@
+Normal rank
@@ Property / cites work @@
+Solving #SAT and MAXSAT by Dynamic Programming
@@ Property / cites work: Solving #SAT and MAXSAT by Dynamic Programming / rank @@
+Normal rank
@@ Property / cites work @@
+Call routing and the ratcatcher
@@ Property / cites work: Call routing and the ratcatcher / rank @@
+Normal rank