Optimal centrality computations within bounded clique-width graphs

DOI10.4230/LIPICS.IPEC.2021.16MaRDI QIDQ6192484zbMATH OpenOpenAlexFDO

Authors Guillaume Ducoffe

Publication date 12 February 2024

Full work available at URL https://hal.science/hal-03445484

zbMATH Keywords

graph theoryclique-widthfacility location problemscentralities computationdistance-labeling schemefine-grained complexity in P

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68Wxx) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• Optimal centrality computations within bounded clique-width graphs
• Efficient parameterized algorithms for computing all-pairs shortest paths
• Efficient parameterized algorithms for computing all-pairs shortest paths
• Compact representation of graphs of small clique-width
• Inductive computations on graphs defined by clique-width expressions

Cited in

(1)

• Obstructions to faster diameter computation: asteroidal sets

This page was built for publication: Optimal centrality computations within bounded clique-width graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6192484)