Optimal centrality computations within bounded clique-width graphs
From MaRDI portal
Publication:2093567
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
Cites work
- A characterisation of clique-width through nested partitions
- A Natural Generalization of Bounded Tree-Width and Bounded Clique-Width
- Algorithms for graphs of bounded treewidth via orthogonal range searching
- Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
- Approximating clique-width and branch-width
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- Bounding the clique-width of \(H\)-free split graphs
- Bounding the Clique‐Width of H‐Free Chordal Graphs
- Characterizing multiterminal flow networks and computing flows in networks of small treewidth
- Chordal bipartite graphs of bounded tree- and clique-width
- Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width
- Classifying the clique-width of \(H\)-free bipartite graphs
- Clique-width for 4-vertex forbidden subgraphs
- Clique-width is NP-complete
- Clique-width of graphs defined by one-vertex extensions
- Clique-width of partner-limited graphs
- Clique-width. III: Hamiltonian cycle and the odd case of graph coloring
- Collective tree spanners in graphs with bounded parameters
- Compact representation of graphs of small clique-width
- Decomposition of Directed Graphs
- Distance labeling in graphs
- Distance labeling scheme and split decomposition
- Efficient and Adaptive Parameterized Algorithms on Modular Decompositions
- Efficient parameterized algorithms for computing all-pairs shortest paths
- Fast Algorithms for Finding Nearest Common Ancestors
- Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
- Fully polynomial-time parameterized computations for graphs and matrices of low treewidth
- GEM- AND CO-GEM-FREE GRAPHS HAVE BOUNDED CLIQUE-WIDTH
- Graph theory
- Graph theory
- scientific article; zbMATH DE number 2044928 (Why is no real title available?)
- scientific article; zbMATH DE number 1512682 (Why is no real title available?)
- scientific article; zbMATH DE number 5279372 (Why is no real title available?)
- Intractability of clique-width parameterizations
- Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
- Linear time solvable optimization problems on graphs of bounded clique-width
- New graph classes of bounded clique-width
- On powers of graphs of bounded NLC-width (clique-width)
- On the clique-width of graph with few \(P_{4}\)'s
- On the clique-width of some perfect graph classes
- On the power of tree-depth for fully polynomial FPT algorithms
- On the Relationship Between Clique-Width and Treewidth
- Parameterized Algorithms for Modular-Width
- Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
- Query efficient implementation of graphs of bounded clique-width
- The \(b\)-matching problem in distance-hereditary graphs and beyond
- The centrality index of a graph
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- The use of a pruned modular decomposition for maximum matching algorithms on some graph classes
- Undirected single-source shortest paths with positive integer weights in linear time
Cited in
(8)- Faster computation of successive bounds on the group betweenness centrality
- scientific article; zbMATH DE number 7075920 (Why is no real title available?)
- Efficient parameterized algorithms for computing all-pairs shortest paths
- Optimal centrality computations within bounded clique-width graphs
- _i-metric graphs: radius, diameter and all eccentricities
- Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
- The complexity of diameter on H-free graphs
- The complexity of diameter on \(H\)-free graphs
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 Q2093567)
