On the tractability of optimization problems on H-graphs
From MaRDI portal
Publication:2196605
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)
Recommendations
Cites work
- scientific article; zbMATH DE number 1420907 (Why is no real title available?)
- scientific article; zbMATH DE number 7378700 (Why is no real title available?)
- Algorithmic graph theory and perfect graphs
- 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
- Boolean-width of graphs
- Combinatorial problems on \(H\)-graphs
- Dominating Sets in Chordal Graphs
- Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
- Fundamentals of parameterized complexity
- Graph classes with structured neighborhoods and algorithmic applications
- Graph classes with structured neighborhoods and algorithmic applications
- Kernelization. Theory of parameterized preprocessing
- Large Induced Subgraphs via Triangulations and CMSO
- Mim-width. III. Graph powers and generalized distance domination problems
- On \(H\)-topological intersection graphs
- 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
- Parameterized algorithms
- Polynomial-Time Algorithm for the Leafage of Chordal Graphs
- Polynomial-time algorithms for the longest induced path and induced disjoint paths problems on graphs of bounded mim-width
- Precoloring extension. I: Interval graphs
- Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- The leafage of a chordal graph
- Treewidth and minimum fill-in: Grouping the minimal separators
Cited in
(21)- Generalized distance domination problems and their complexity on graphs of bounded mim-width
- scientific article; zbMATH DE number 7561685 (Why is no real title available?)
- Testing isomorphism of chordal graphs of bounded leafage is fixed-parameter tractable (extended abstract)
- Treewidth versus clique number. II: Tree-independence number
- scientific article; zbMATH DE number 7764113 (Why is no real title available?)
- Combinatorial problems on \(H\)-graphs
- Parameterized complexity of multicut in weighted trees
- 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
- Parameterized algorithms for Steiner tree and dominating set: bounding the leafage by the vertex leafage
- Intersection graphs of non-crossing paths
- Finding optimal triangulations parameterized by edge clique cover
- Fair allocation algorithms for indivisible items under structured conflict constraints
- 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)
