Graph-Theoretic Concepts in Computer Science

DOI10.1007/b104584zbMath1112.68420OpenAlexW4211210842MaRDI QIDQ5710806

Dieter Kratsch, Fedor V. Fomin, Gerhard J. Woeginger

Publication date: 8 December 2005

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/b104584

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (35)

A Faster Algorithm for Dominating Set Analyzed by the Potential Method ⋮ Assigning channels via the meet-in-the-middle approach ⋮ Parameterized complexity dichotomy for \textsc{Steiner Multicut} ⋮ Parameterized complexity of graph burning ⋮ Analyzing the reachability problem in choice networks ⋮ The graph motif problem parameterized by the structure of the input graph ⋮ Exact Exponential Algorithms to Find a Tropical Connected Set of Minimum Size ⋮ Exact algorithms for dominating set ⋮ Exact algorithms for edge domination ⋮ Solving Capacitated Dominating Set by using covering by subsets and maximum matching ⋮ Lower bounds on kernelization ⋮ An exact algorithm for the minimum dominating clique problem ⋮ Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs ⋮ Parameterized Complexity of Graph Burning ⋮ Inclusion/exclusion meets measure and conquer ⋮ Solving connected dominating set faster than \(2^n\) ⋮ Exact exponential algorithms to find tropical connected sets of minimum size ⋮ Finding a dominating set on bipartite graphs ⋮ Unnamed Item ⋮ Solving Capacitated Dominating Set by Using Covering by Subsets and Maximum Matching ⋮ Dynamic parameterized problems ⋮ Finding large degree-anonymous subgraphs is hard ⋮ The complexity ecology of parameters: An illustration using bounded max leaf number ⋮ Efficiency in exponential time for domination-type problems ⋮ Parameterized complexity of conflict-free set cover ⋮ Fine-grained complexity of safety verification ⋮ On two techniques of combining branching and treewidth ⋮ Fine-Grained Reductions and Quantum Speedups for Dynamic Programming. ⋮ Vertex and edge covers with clustering properties: Complexity and algorithms ⋮ Unnamed Item ⋮ A randomized algorithm for determining dominating sets in graphs of maximum degree five ⋮ Refined parameterizations for computing colored cuts in edge-colored graphs ⋮ On the Complexity of Bounded Context Switching. ⋮ Pathwidth of cubic graphs and exact algorithms ⋮ Multiple Hypernode Hitting Sets and Smallest Two-Cores with Targets

This page was built for publication: Graph-Theoretic Concepts in Computer Science