Partition on trees with supply and demand: kernelization and algorithms

DOI10.1016/j.tcs.2016.06.044zbMath1356.68104OpenAlexW2466022259MaRDI QIDQ507429

Wenjun Li, Qilong Feng, Mugang Lin, Jian'er Chen

Publication date: 6 February 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2016.06.044

zbMATH Keywords

fixed-parameter tractabilitybranching algorithmkernelizatonnetwork reconfiguration

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Deterministic network models in operations research (90B10)

Related Items (6)

Dealing with several parameterized problems by random methods ⋮ Parameterized algorithms for edge biclique and related problems ⋮ Improved PTAS for the constrained \(k\)-means problem ⋮ An improved FPT algorithm for almost forest deletion problem ⋮ An approximation algorithm for the \(l\)-pseudoforest deletion problem ⋮ An improved linear kernel for complementary maximal strip recovery: simpler and smaller

Cites Work

• Unnamed Item
• A heuristic method for solving the problem of partitioning graphs with supply and demand
• A parameterized study of maximum generalized pattern matching problems
• Fundamentals of parameterized complexity
• Parameterized complexity of Min-power multicast problems in wireless ad hoc networks
• Matching and weighted \(P_2\)-packing: algorithms and kernels
• Improved parameterized algorithms for minimum link-length rectilinear spanning path problem
• Tree \(t\)-spanners in outerplanar graphs via supply demand partition
• Partitioning graphs of supply and demand
• Approximability of partitioning graphs with supply and demand
• Minimum cost partitions of trees with supply and demand
• Facility location problems: a parameterized view
• Parametric power supply networks
• Randomized parameterized algorithms for \(P_2\)-packing and co-path packing problems
• Parameterized complexity of control and bribery for \(d\)-approval elections
• Dealing with 4-Variables by Resolution: An Improved MaxSAT Algorithm
• Modelling the Power Supply Network – Hardness and Approximation
• PARTITIONING TREES OF SUPPLY AND DEMAND
• Parameterized Algorithms

This page was built for publication: Partition on trees with supply and demand: kernelization and algorithms