On \(H\)-topological intersection graphs

DOI10.1007/s00453-021-00846-3OpenAlexW4206152305MaRDI QIDQ5925535

Jan Voborník, Steven Chaplick, Peter Zeman, Martin Töpfer

Publication date: 19 November 2021

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-021-00846-3

zbMATH Keywords

treewidthrecognitiondominating setcoloringmaximum cliquegraph isomorphismminimal separatorsH-graphsNP-completess

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Related Items (4)

Fair allocation algorithms for indivisible items under structured conflict constraints ⋮ Treewidth versus clique number. II: Tree-independence number ⋮ Solving problems on generalized convex graphs via mim-width ⋮ Intersection graphs of non-crossing paths

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reduced clique graphs of chordal graphs
• Bounded coloring of co-comparability graphs and the pickup and delivery tour combination problem
• Graph minors. III. Planar tree-width
• Decomposition by clique separators
• Precoloring extension. I: Interval graphs
• The complexity of comparability graph recognition and coloring
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Generalized coloring for tree-like graphs
• Combinatorial problems on \(H\)-graphs
• Algorithmic graph theory and perfect graphs
• Intersection graphs of Helly families of subtrees
• On the tractability of optimization problems on \(H\)-graphs
• Mim-width. II. The feedback vertex set problem
• Extending partial representations of subclasses of chordal graphs
• The maximum clique problem in multiple interval graphs
• Incidence matrices and interval graphs
• The vertex leafage of chordal graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• The stable set problem and the thinness of a graph
• Treewidth and Minimum Fill-in: Grouping the Minimal Separators
• A $c^k n$ 5-Approximation Algorithm for Treewidth
• Large Induced Subgraphs via Triangulations and CMSO
• Note on Dilworth's Decomposition Theorem for Partially Ordered Sets
• The Complexity of the Partial Order Dimension Problem
• Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs
• Dominating Sets in Chordal Graphs
• Algorithms on circular-arc graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• Minimum Fill-in on Circle and Circular-Arc Graphs
• Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
• On the structure of (pan, even hole)‐free graphs
• On the number of minimal separators in graphs
• Determining DNA sequence similarity using maximum independent set algorithms for interval graphs
• On List Coloring and List Homomorphism of Permutation and Interval Graphs
• Algorithm Theory - SWAT 2004
• Bidimensional Parameters and Local Treewidth
• The Complexity of Combinatorial Optimization Problems on d‐Dimensional Boxes
• Parameterized Algorithms
• Topology of Thin Film RC Circuits
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• On \(H\)-topological intersection graphs

This page was built for publication: On \(H\)-topological intersection graphs