Well-partitioned chordal graphs

DOI10.1016/j.disc.2022.112985zbMath1491.05146OpenAlexW4280652960MaRDI QIDQ2144581

Lars Jaffke, Jungho Ahn, Paloma T. Lima, O-joung Kwon

Publication date: 14 June 2022

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2022.112985

zbMATH Keywords

forbidden induced subgraphsgeodetic settree spannergraph classwell-partitioned chordal graphlongest path transversal

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Connectivity (05C40)

Related Items (2)

Algorithms and complexity for geodetic sets on partial grids ⋮ \(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximating the \textsc{Sparsest} \(k\)-\textsc{Subgraph} in chordal graphs
• Detour trees
• Fundamentals of parameterized complexity
• Intersecting longest paths
• A characterization of substar graphs
• Certifying algorithms
• Tree 3-spanners in 2-sep chordal graphs: characterization and algorithms
• Tree 3-spanners on interval, permutation and regular bipartite graphs
• Subtree and substar intersection numbers
• Nonempty intersection of longest paths in series-parallel graphs
• Hardness and approximation for the geodetic set problem in some graph classes
• Dominating sets for split and bipartite graphs
• Tree spanners for bipartite graphs and probe interval graphs
• Detecting holes and antiholes in graphs
• Some remarks on the geodetic number of a graph
• Clustering and domination in perfect graphs
• On sparse spanners of weighted graphs
• On the pathwidth of chordal graphs
• The geodetic number of a graph
• Restrictions of minimum spanner problems
• Nonempty intersection of longest paths in \(2K_2\)-free graphs
• On the hardness of finding the geodetic number of a subcubic graph
• Graphs with small fall-spectrum
• \(b\)-coloring of tight graphs
• Polynomial time algorithm for computing a minimum geodetic set in outerplanar graphs
• Tree spanners on chordal graphs: complexity and algorithms
• Algorithmic graph theory and perfect graphs
• HAMILTONian circuits in chordal bipartite graphs
• Well-partitioned chordal graphs: obstruction set and disjoint paths
• Incidence matrices and interval graphs
• Lower bounds on the mim-width of some graph classes
• A note on longest paths in circular arc graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Three problems on well-partitioned chordal graphs
• Geodesic Convexity in Graphs
• Computing Minimum Geodetic Sets of Proper Interval Graphs
• Optimal On-Line Simulations of Tree Machines by Random Access Machines
• On longest paths and circuits in graphs.
• Algorithmic Aspects of Vertex Elimination on Graphs
• Graph Classes: A Survey
• Computational Complexity of Geodetic Set
• Kernelization
• Longest Paths in Circular Arc Graphs
• Tree Spanners
• Transversals of Longest Paths and Cycles
• Parameterized Algorithms
• Intersection of longest paths in graph classes
• Transversals of longest paths
• Tree spanners in planar graphs
• Parameterized Complexity of Geodetic Set

This page was built for publication: Well-partitioned chordal graphs