Optimal centrality computations within bounded clique-width graphs
type: Item
instance of: scholarly article
title: Optimal centrality computations within bounded clique-width graphs
author: Guillaume Ducoffe
published in: Algorithmica
publication date: 2022-10-27T00:00:00Z
Mathematics Subject Classification ID: 68Wxx
Mathematics Subject Classification ID: 05Cxx
zbMATH DE Number: 7608288
zbMATH Keywords: clique-width
zbMATH Keywords: centralities computation
zbMATH Keywords: facility location problems
zbMATH Keywords: distance-labeling scheme
zbMATH Keywords: fine-grained complexity in P
zbMATH Keywords: graph theory
MaRDI profile type: Publication
full work available at URL: s00453-022-01015-w
OpenAlex ID: W4289866354
cites work: Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
cites work: Q5422499
cites work: Bounding the clique-width of \(H\)-free split graphs
cites work: Bounding the Clique‐Width of H‐Free Chordal Graphs
cites work: New graph classes of bounded clique-width
cites work: Clique-width for 4-vertex forbidden subgraphs
cites work: Q5387674
cites work: GEM- AND CO-GEM-FREE GRAPHS HAVE BOUNDED CLIQUE-WIDTH
cites work: Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width
cites work: Algorithms for graphs of bounded treewidth via orthogonal range searching
cites work: Q4508369
cites work: On the Relationship Between Clique-Width and Treewidth
cites work: Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs
cites work: The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
cites work: A characterisation of clique-width through nested partitions
cites work: Linear time solvable optimization problems on graphs of bounded clique-width
cites work: Query efficient implementation of graphs of bounded clique-width
cites work: Decomposition of Directed Graphs
cites work: Classifying the clique-width of \(H\)-free bipartite graphs
cites work: Q3577833
cites work: Collective tree spanners in graphs with bounded parameters
cites work: Q5091021
cites work: Q5090996
cites work: Q4448752
cites work: Clique-Width is NP-Complete
cites work: Intractability of Clique-Width Parameterizations
cites work: Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
cites work: Clique-width III
cites work: Fully Polynomial-Time Parameterized Computations for Graphs and Matrices of Low Treewidth
cites work: A Natural Generalization of Bounded Tree-Width and Bounded Clique-Width
cites work: Parameterized Algorithms for Modular-Width
cites work: Distance labeling scheme and split decomposition
cites work: Distance labeling in graphs
cites work: Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
cites work: ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
cites work: Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
cites work: Characterizing multiterminal flow networks and computing flows in networks of small treewidth
cites work: Fast Algorithms for Finding Nearest Common Ancestors
cites work: On the Power of Tree-Depth for Fully Polynomial FPT Algorithms
cites work: Compact representation of graphs of small clique-width
cites work: Efficient and Adaptive Parameterized Algorithms on Modular Decompositions
cites work: Q5874311
cites work: Chordal bipartite graphs of bounded tree- and clique-width
cites work: ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P4'S
cites work: Approximating clique-width and branch-width
cites work: Clique-width of graphs defined by one-vertex extensions
cites work: The centrality index of a graph
cites work: On powers of graphs of bounded NLC-width (clique-width)
cites work: Undirected single-source shortest paths with positive integer weights in linear time
cites work: Clique-width of partner-limited graphs
DOI: 10.1007/S00453-022-01015-W
description: scientific article; zbMATH DE number 7608288