On the tractability of optimization problems on H-graphs
From MaRDI portal
Publication:2196605
Graph representations (geometric and intersection representations, etc.) (05C62) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial optimization (90C27)
Recommendations
Cites work
- 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
- scientific article; zbMATH DE number 1420907 (Why is no real title available?)
- 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
- On the tractability of optimization problems on \(H\)-graphs
- 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
(32)- Combinatorial problems on \(H\)-graphs
- 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
- Tractable Optimization Problems through Hypergraph-Based Structural Restrictions
- Kernelization of graph Hamiltonicity: proper \(H\)-graphs
- Generalized distance domination problems and their complexity on graphs of bounded mim-width
- On the tractability of optimization problems on \(H\)-graphs
- Reducing the domination number of graphs via edge contractions
- On \(H\)-topological intersection graphs
- On \(H\)-topological intersection graphs
- Intersection graphs of non-crossing paths
- 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
- Recognizing Proper Tree-Graphs
- scientific article; zbMATH DE number 7764113 (Why is no real title available?)
- Computing a minimum subset feedback vertex set on chordal graphs parameterized by leafage
- Treewidth versus clique number. II: Tree-independence number
- Classes of intersection digraphs with good algorithmic properties
- Domination and Cut Problems on Chordal Graphs with Bounded Leafage
- Testing isomorphism of chordal graphs of bounded leafage is fixed-parameter tractable
- Computing tree decompositions with small independence number
- Finding induced subgraphs from graphs with small mim-width
- The simultaneous interval number: a new width parameter that measures the similarity to interval graphs
- Domination and cut problems on chordal graphs with bounded leafage
- XNLP-completeness for parameterized problems on graphs with a linear structure
- On the hardness of generalized domination problems parameterized by mim-width
- XNLP-completeness for parameterized problems on graphs with a linear structure
- Non-crossing H-graphs: a generalization of proper interval graphs admitting FPT algorithms
- On algorithmic applications of \(\mathcal{F}\)-branchwidth
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)
