Hardness and efficiency on minimizing maximum distances for graphs with few \(P_4\)'s and \((k, \ell)\)-graphs

DOI10.1016/j.entcs.2019.08.032OpenAlexW2978275643WikidataQ113317400 ScholiaQ113317400MaRDI QIDQ2132367

Fernanda Couto, Luís Cunha

Publication date: 27 April 2022

Full work available at URL: https://doi.org/10.1016/j.entcs.2019.08.032

zbMATH Keywords

\((2, 1)\)-chordal graphs\((k, \ell)\)-graphs\textsf{P} vs \textsf{NP}-c dichotomygraphs with few \(P_4\)'sstretch index

Mathematics Subject Classification ID

Mathematical programming (90Cxx) Graph theory (05Cxx)

Related Items (3)

Strategies for generating tree spanners: algorithms, heuristics and optimal graph classes ⋮ Hardness and efficiency on \(t\)-admissibility for graph operations ⋮ Edge tree spanners

Cites Work

• Unnamed Item
• Tree 3-spanners in 2-sep chordal graphs: characterization and algorithms
• On the minimum diameter spanning tree problem
• Tree spanners for bipartite graphs and probe interval graphs
• A tree representation for \(P_ 4\)-sparse graphs
• Tree spanners on chordal graphs: complexity and algorithms
• Partitions of graphs into one or two independent sets and cliques
• Tree \(t\)-spanners of a graph: minimizing maximum distances efficiently
• Tree Spanners
• P-Components and the Homogeneous Decomposition of Graphs
• Advancing the Transposition Distance and Diameter through Lonely Permutations
• Min-Max Graph Partitioning and Small Set Expansion

This page was built for publication: Hardness and efficiency on minimizing maximum distances for graphs with few \(P_4\)'s and \((k, \ell)\)-graphs