Graph-Theoretic Concepts in Computer Science
From MaRDI portal
Publication:5710807
DOI10.1007/b104584zbMath1112.68412OpenAlexW4211210842MaRDI QIDQ5710807
Michael R. Fellows, David W. Juedes, Benny Chor
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
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Linear kernels for separating a graph into components of bounded size ⋮ Linear-Time Computation of a Linear Problem Kernel for Dominating Set on Planar Graphs ⋮ A \((2 + \epsilon ) k\)-vertex kernel for the dual coloring problem ⋮ Parameterizing role coloring on forests ⋮ Exploiting $c$-Closure in Kernelization Algorithms for Graph Problems ⋮ Kernelization – Preprocessing with a Guarantee ⋮ On the kernelization of split graph problems ⋮ Saving Colors and Max Coloring: Some Fixed-Parameter Tractability Results ⋮ On a generalization of Nemhauser and Trotter's local optimization theorem ⋮ Induced star partition of graphs ⋮ List-coloring -- parameterizing from triviality ⋮ Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter ⋮ Linear kernels for outbranching problems in sparse digraphs ⋮ A refined algorithm for maximum independent set in degree-4 graphs ⋮ Preprocessing to reduce the search space: antler structures for feedback vertex set ⋮ Data reduction for graph coloring problems ⋮ Kernelization for feedback vertex set via elimination distance to a forest ⋮ Data Reduction for Maximum Matching on Real-World Graphs ⋮ An exact algorithm for maximum independent set in degree-5 graphs ⋮ Kernelization for feedback vertex set via elimination distance to a forest ⋮ On the Parameterized Parallel Complexity and the Vertex Cover Problem ⋮ On bounded block decomposition problems for under-specified systems of equations ⋮ What Is Known About Vertex Cover Kernelization? ⋮ Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack ⋮ A generalization of Nemhauser and Trotter's local optimization theorem ⋮ Kernelization of Two Path Searching Problems on Split Graphs ⋮ Why Is Maximum Clique Often Easy in Practice? ⋮ Exploiting c-Closure in Kernelization Algorithms for Graph Problems ⋮ Dual parameterization of Weighted Coloring ⋮ Crown reductions for the minimum weighted vertex cover problem ⋮ Faster fixed-parameter tractable algorithms for matching and packing problems ⋮ Saving colors and max coloring: some fixed-parameter tractability results ⋮ Improved upper bounds for vertex cover ⋮ Kernels for packing and covering problems ⋮ A kernelization algorithm for \(d\)-hitting set ⋮ Hitting Forbidden Minors: Approximation and Kernelization ⋮ Parameterized certificate dispersal and its variants ⋮ The complexity ecology of parameters: An illustration using bounded max leaf number ⋮ Fixed-parameter tractability of \((n-k)\) list coloring ⋮ Data Reduction for Graph Coloring Problems ⋮ A relaxation of the directed disjoint paths problem: a global congestion metric helps ⋮ A Relaxation of the Directed Disjoint Paths Problem: A Global Congestion Metric Helps. ⋮ An improved kernelization algorithm for \(r\)-set packing ⋮ Efficient parallel algorithms for parameterized problems ⋮ Minimum leaf out-branching and related problems ⋮ Dual parameterization of weighted coloring ⋮ Parameterized Pre-Coloring Extension and List Coloring Problems ⋮ Unnamed Item ⋮ Nearly optimal robust secret sharing against rushing adversaries
Uses Software
