Parameterized complexity of diameter
From MaRDI portal
Publication:5925618
DOI10.1007/s00453-022-01032-9OpenAlexW2788651746MaRDI QIDQ5925618
André Nichterlein, Matthias Bentert
Publication date: 16 February 2023
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-022-01032-9
Graph theory (including graph drawing) in computer science (68R10) Parameterized complexity, tractability and kernelization (68Q27)
Cites Work
- Multivariate analysis of orthogonal range searching and graph distances
- On the all-pairs-shortest-path problem in unweighted undirected graphs.
- Which problems have strongly exponential complexity?
- The power of linear-time data reduction for maximum matching
- Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs
- Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
- A Simple Linear Time LexBFS Cograph Recognition Algorithm
- A Linear Recognition Algorithm for Cographs
- Efficient Algorithms for Shortest Paths in Sparse Networks
- Graph Classes: A Survey
- Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
- The Structure and Function of Complex Networks
- Solving the all-pair shortest path query problem on interval and circular-arc graphs
- Community structure in social and biological networks
- Fully Polynomial-Time Parameterized Computations for Graphs and Matrices of Low Treewidth
- New Bounds for Approximating Extremal Distances in Undirected Graphs
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- Linear Recognition of Almost Interval Graphs
- An Axiomatic and an Average-Case Analysis of Algorithms and Heuristics for Metric Properties of Graphs
- Approximating the Diameter of Planar Graphs in Near Linear Time
- Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs
- Efficient and Adaptive Parameterized Algorithms on Modular Decompositions
- Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
- Deterministic APSP, Orthogonal Vectors, and More
- Data Reduction for Maximum Matching on Real-World Graphs
- An Adaptive Version of Brandes' Algorithm for Betweenness Centrality
- Diameter computation on H-minor free graphs and graphs of bounded (distance) VC-dimension
- O(1) QUERY TIME ALGORITHM FOR ALL PAIRS SHORTEST DISTANCES ON INTERVAL GRAPHS
- Parameterized and Exact Computation
- Fast approximation algorithms for the diameter and radius of sparse graphs
- Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time
- Networks
- Parameterized aspects of triangle enumeration
- When can graph hyperbolicity be computed in linear time?
- On the complexity of \(k\)-SAT
This page was built for publication: Parameterized complexity of diameter
