scientific article; zbMATH DE number 7278055

DOI10.4230/LIPIcs.ISAAC.2017.50zbMath1457.68126MaRDI QIDQ5136270

Ioannis Katsikarelis, Michael Lampis, Vangelis Th. Paschos

Publication date: 25 November 2020

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

approximationtreewidthdominationclique-widthFPT algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (6)

Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs ⋮ Parameterized approximation algorithms for some location problems in graphs ⋮ Travelling on graphs with small highway dimension ⋮ Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation ⋮ Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation ⋮ The Parameterized Hardness of the k-Center Problem in Transportation Networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The \(k\)-hop connected dominating set problem: hardness and polyhedra
• Fundamentals of parameterized complexity
• Treewidth. Computations and approximations
• Fault tolerant \(K\)-center problems
• Exact and approximation algorithms for clustering
• Which problems have strongly exponential complexity?
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Parameterized edge Hamiltonicity
• Faster algorithms for vertex partitioning problems parameterized by clique-width
• Parametrized complexity theory.
• Tree-depth, subgraph coloring and homomorphism bounds
• Hardness of r-dominating set on Graphs of Diameter (r + 1)
• Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
• Parameterized Power Vertex Cover
• Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs
• Treewidth: Characterizations, Applications, and Computations
• Fourier meets M\"{o}bius: fast subset convolution
• Faster Algorithms on Branch and Clique Decompositions
• Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
• R -Domination in Graphs
• Parallel Algorithms with Optimal Speedup for Bounded Treewidth
• AnO(log*n) Approximation Algorithm for the Asymmetricp-Center Problem
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• The Capacitated K-Center Problem
• A linear-time algorithm for connectedr-domination and Steiner tree on distance-hereditary graphs
• Optimal dynamic program for r-domination problems over tree decompositions
• Practical algorithms on partial k-trees with an application to domination-like problems
• Parameterized Approximation Schemes Using Graph Widths
• Parameterized Complexity for Domination Problems on Degenerate Graphs
• Approximating k-center in planar graphs
• Algorithms – ESA 2005
• Parameterized Algorithms
• Parameterized approximation algorithms for some location problems in graphs
• On the complexity of \(k\)-SAT

This page was built for publication: