On the tractability of optimization problems on H-graphs
DOI10.1007/S00453-020-00692-9zbMATH Open1447.05142OpenAlexW2759740247MaRDI QIDQ2196605FDOQ2196605
Authors: Fedor V. Fomin, Jean-Florent Raymond, 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
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph representations (geometric and intersection representations, etc.) (05C62)
Cites Work
- Fundamentals of parameterized complexity
- Algorithmic graph theory and perfect graphs
- Parameterized algorithms
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Large Induced Subgraphs via Triangulations and CMSO
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- The leafage of a chordal graph
- On the parameterized complexity of multiple-interval graph problems
- On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
- Treewidth and minimum fill-in: Grouping the minimal separators
- Dominating Sets in Chordal Graphs
- Boolean-width of graphs
- Graph classes with structured neighborhoods and algorithmic applications
- Polynomial-Time Algorithm for the Leafage of Chordal Graphs
- Precoloring extension. I: Interval graphs
- Graph classes with structured neighborhoods and algorithmic applications
- Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
- Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
- Title not available (Why is that?)
- Kernelization. Theory of parameterized preprocessing
- Polynomial-time algorithms for the longest induced path and induced disjoint paths problems on graphs of bounded mim-width
- Combinatorial problems on \(H\)-graphs
- Mim-width. III. Graph powers and generalized distance domination problems
- On \(H\)-topological intersection graphs
- Title not available (Why is that?)
Cited In (21)
- Generalized distance domination problems and their complexity on graphs of bounded mim-width
- Title not available (Why is that?)
- Testing isomorphism of chordal graphs of bounded leafage is fixed-parameter tractable (extended abstract)
- Treewidth versus clique number. II: Tree-independence number
- Title not available (Why is that?)
- Parameterized complexity of multicut in weighted trees
- Combinatorial problems on \(H\)-graphs
- On \(H\)-topological intersection graphs
- Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage
- On \(H\)-topological intersection graphs
- Recognizing Proper Tree-Graphs
- Intersection graphs of non-crossing paths
- Parameterized algorithms for Steiner tree and dominating set: bounding the leafage by the vertex leafage
- Fair allocation algorithms for indivisible items under structured conflict constraints
- Finding optimal triangulations parameterized by edge clique cover
- Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage
- Classes of intersection digraphs with good algorithmic properties
- Domination and Cut Problems on Chordal Graphs with Bounded Leafage
- Kernelization of graph Hamiltonicity: proper \(H\)-graphs
- Bounding the mim‐width of hereditary graph classes
- Tractable Optimization Problems through Hypergraph-Based Structural Restrictions
This page was built for publication: On the tractability of optimization problems on \(H\)-graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2196605)
