Graph-Theoretic Concepts in Computer Science

DOI10.1007/b104584zbMath1112.68418OpenAlexW4211210842MaRDI QIDQ5710805

Frances A. Rosamond, Christian Sloper, Jan Arne Telle, Michael R. Fellows, Pinar Heggernes

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) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (26)

Linear-vertex kernel for the problem of packing \(r\)-stars into a graph without long induced paths ⋮ Looking at the stars ⋮ Edge-disjoint packing of stars and cycles ⋮ An \(O^*(1.4366^n)\)-time exact algorithm for maximum \(P_2\)-packing in cubic graphs ⋮ Parameterized counting matching and packing: a family of hard problems that admit FPTRAS ⋮ Dealing with several parameterized problems by random methods ⋮ Edge-Disjoint Packing of Stars and Cycles ⋮ Narrow sieves for parameterized paths and packings ⋮ Polynomial kernelization for removing induced claws and diamonds ⋮ The control complexity of \(r\)-Approval: from the single-peaked case to the general case ⋮ Linear kernels for outbranching problems in sparse digraphs ⋮ Matching and weighted \(P_2\)-packing: algorithms and kernels ⋮ Kernelization Algorithms for Packing Problems Allowing Overlaps ⋮ Confronting intractability via parameters ⋮ Improved Algorithms for Several Parameterized Problems Based on Random Methods ⋮ Arbitrary Overlap Constraints in Graph Packing Problems ⋮ Crown reductions for the minimum weighted vertex cover problem ⋮ Parameterized algorithms for weighted matching and packing problems ⋮ Faster fixed-parameter tractable algorithms for matching and packing problems ⋮ Improved upper bounds for vertex cover ⋮ A Problem Kernelization for Graph Packing ⋮ An improved kernelization for \(P_{2}\)-packing ⋮ Using Parametric Transformations Toward Polynomial Kernels for Packing Problems Allowing Overlaps ⋮ Minimum leaf out-branching and related problems ⋮ Unnamed Item ⋮ Randomized parameterized algorithms for \(P_2\)-packing and co-path packing problems

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