Beyond Classes of Graphs with “Few” Minimal Separators: FPT Results Through Potential Maximal Cliques

DOI10.1007/978-3-662-53174-7_35MaRDI QIDQ2827832zbMATH OpenOpenAlexFDO

Authors Mathieu Liedloff, Pedro Montealegre, Ioan Todinca

Publication date 21 October 2016

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-53174-7_35

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• Beyond classes of graphs with ``few minimal separators: FPT results through potential maximal cliques
• Covering minimal separators and potential maximal cliques in \(P_t\)-free graphs
• Finding a maximum minimal separator: graph classes and fixed-parameter tractability
• scientific article; zbMATH DE number 1305094
• On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
• On Clique Separators, Nearly Chordal Graphs, and the Maximum Weight Stable Set Problem
• Minimum \((n,k,t)\) clique graphs
• scientific article; zbMATH DE number 4134082
• Minimizing the numbers of cliques and cycles of fixed size in an \(F\)-saturated graph
• On the minimum number of \(k\)-cliques in graphs with restricted independence number

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• A partial k-arboretum of graphs with bounded treewidth
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• Chordal deletion is fixed-parameter tractable
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Finding induced subgraphs via minimal triangulations
• Fixed-parameter tractability of treewidth and pathwidth
• GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH
• Graph minors. XX: Wagner's conjecture
• Graph structure and monadic second-order logic. A language-theoretic approach
• Independent packings in structured graphs
• Large Induced Subgraphs via Triangulations and CMSO
• Listing all potential maximal cliques of a graph
• Minimum fill-in and treewidth of split \(+ ke\) and split \(+kv\) graphs
• Parameterized complexity of vertex deletion into perfect graph classes
• The complexity of first-order and monadic second-order logic revisited
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Treewidth and minimum fill-in: Grouping the minimal separators
• Upper bounds on the size of obstructions and intertwines

Cited in

(3)

• On distance-\(d\) Independent Set and other problems in graphs with ``few minimal separators
• Taming graphs with no large creatures and skinny ladders
• Beyond classes of graphs with ``few minimal separators: FPT results through potential maximal cliques

This page was built for publication: Beyond Classes of Graphs with “Few” Minimal Separators: FPT Results Through Potential Maximal Cliques

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2827832)