Fast Diameter Computation within Split Graphs (Q5024674)

scientific article; zbMATH DE number 7465231

Language	Label	Description	Also known as
English	Fast Diameter Computation within Split Graphs	scientific article; zbMATH DE number 7465231

Statements

instance of

scholarly article

0 references

title

Fast Diameter Computation within Split Graphs (English)

0 references

0 references

0 references

0 references

Discrete Mathematics & Theoretical Computer Science

0 references

publication date

27 January 2022

0 references

full work available at URL

https://dmtcs.episciences.org/8680

0 references

zbMATH Keywords

graph diameter

0 references

split graphs

0 references

interval representations

0 references

fine-grained complexity

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs

0 references

Scheduling Split Intervals

0 references

Decomposable searching problems

0 references

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

0 references

Q4288578

0 references

Q5422499

0 references

Into the square: on the complexity of some quadratic-time solvable problems

0 references

Identifying Codes in Hereditary Classes of Graphs and VC-Dimension

0 references

The algorithmic use of hypertree structure and maximum neighbourhood orderings

0 references

Distance Approximating Trees for Chordal and Dually Chordal Graphs

0 references

Tree spanners on chordal graphs: complexity and algorithms

0 references

Rooted directed path graphs are leaf powers

0 references

Q5009466

0 references

Lower bounds for orthogonal range searching: I. The reporting case

0 references

Quasi-optimal range searching in spaces of finite VC-dimension

0 references

Diameter determination on restricted graph families

0 references

Q4437127

0 references

Estimating all pairs shortest paths in restricted graph families: a unified approach

0 references

Fast diameter computation within split graphs

0 references

Diameter computation on <i>H</i>-minor free graphs and graphs of bounded (distance) VC-dimension

0 references

Central limit theorems for empirical measures

0 references

Characterizations of strongly chordal graphs

0 references

Incidence matrices and interval graphs

0 references

Algorithmic graph theory and perfect graphs

0 references

Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing

0 references

Q5503435

0 references

Three ways to cover a graph

0 references

Domination on Cocomparability Graphs

0 references

Modular decomposition and transitive orientation

0 references

A simple linear-time algorithm for computing the center of an interval graph

0 references

Fast approximation algorithms for the diameter and radius of sparse graphs

0 references

On the density of families of sets

0 references

The interval number of a planar graph: Three intervals suffice

0 references

A combinatorial problem; stability and order for models and theories in infinitary languages

0 references

Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs

0 references

Recognizing graphs with fixed interval number is NP-complete

0 references

Identifiers

zbMATH Open document ID

1481.05040

0 references

DOI

10.46298/dmtcs.6422

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:5024674