On the tractability of optimization problems on \(H\)-graphs

DOI10.1007/s00453-020-00692-9zbMath1447.05142OpenAlexW2759740247MaRDI QIDQ2196605

Jean-Florent Raymond, Fedor V. Fomin, Petr A. Golovach

Publication date: 3 September 2020

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-020-00692-9

zbMATH Keywords

dominating setminimal separatorsmim-width\(H\)-topological intersection graphs

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (17)

Parameterized algorithms for Steiner tree and dominating set: bounding the leafage by the vertex leafage ⋮ Finding optimal triangulations parameterized by edge clique cover ⋮ Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage ⋮ Testing isomorphism of chordal graphs of bounded leafage is fixed-parameter tractable (extended abstract) ⋮ Parameterized complexity of multicut in weighted trees ⋮ Fair allocation algorithms for indivisible items under structured conflict constraints ⋮ Bounding the mim‐width of hereditary graph classes ⋮ Treewidth versus clique number. II: Tree-independence number ⋮ Classes of intersection digraphs with good algorithmic properties ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Recognizing Proper Tree-Graphs ⋮ Intersection graphs of non-crossing paths ⋮ Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage ⋮ Unnamed Item ⋮ On \(H\)-topological intersection graphs ⋮ Kernelization of Graph Hamiltonicity: Proper $H$-Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Graph classes with structured neighborhoods and algorithmic applications
• Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
• Boolean-width of graphs
• Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
• On the parameterized complexity of multiple-interval graph problems
• Precoloring extension. I: Interval graphs
• Combinatorial problems on \(H\)-graphs
• On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
• Algorithmic graph theory and perfect graphs
• Mim-width. III. Graph powers and generalized distance domination problems
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Treewidth and Minimum Fill-in: Grouping the Minimal Separators
• Large Induced Subgraphs via Triangulations and CMSO
• Graph Classes with Structured Neighborhoods and Algorithmic Applications
• Polynomial-Time Algorithm for the Leafage of Chordal Graphs
• Dominating Sets in Chordal Graphs
• The leafage of a chordal graph
• Kernelization
• Parameterized Algorithms
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• On \(H\)-topological intersection graphs

This page was built for publication: On the tractability of optimization problems on \(H\)-graphs