Fast Diameter Computation within Split Graphs
From MaRDI portal
Publication:5024674
DOI10.46298/dmtcs.6422zbMath1481.05040OpenAlexW3212733298MaRDI QIDQ5024674
Laurent Viennot, Guillaume Ducoffe, Michel A. Habib
Publication date: 27 January 2022
Published in: Discrete Mathematics & Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://dmtcs.episciences.org/8680
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Into the square: on the complexity of some quadratic-time solvable problems
- Recognizing graphs with fixed interval number is NP-complete
- The interval number of a planar graph: Three intervals suffice
- Three ways to cover a graph
- Rooted directed path graphs are leaf powers
- Characterizations of strongly chordal graphs
- Central limit theorems for empirical measures
- Decomposable searching problems
- Modular decomposition and transitive orientation
- The algorithmic use of hypertree structure and maximum neighbourhood orderings
- Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
- Quasi-optimal range searching in spaces of finite VC-dimension
- Tree spanners on chordal graphs: complexity and algorithms
- Algorithmic graph theory and perfect graphs
- Fast diameter computation within split graphs
- Incidence matrices and interval graphs
- A combinatorial problem; stability and order for models and theories in infinitary languages
- On the density of families of sets
- Domination on Cocomparability Graphs
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Identifying Codes in Hereditary Classes of Graphs and VC-Dimension
- Lower bounds for orthogonal range searching: I. The reporting case
- A simple linear-time algorithm for computing the center of an interval graph
- Distance Approximating Trees for Chordal and Dually Chordal Graphs
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- Diameter computation on H-minor free graphs and graphs of bounded (distance) VC-dimension
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Scheduling Split Intervals
- Fast approximation algorithms for the diameter and radius of sparse graphs
- Estimating all pairs shortest paths in restricted graph families: a unified approach
- Diameter determination on restricted graph families
This page was built for publication: Fast Diameter Computation within Split Graphs
