Partition on trees with supply and demand: kernelization and algorithms

DOI10.1016/J.TCS.2016.06.044MaRDI QIDQ507429zbMATH OpenOpenAlexFDO

Authors Mugang Lin, Qilong Feng, Wen-Jun Li, Jianer 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) Deterministic network models in operations research (90B10) Nonnumerical algorithms (68W05)

Recommendations

• Parameterized Minimum Cost Partition of a Tree with Supply and Demand
• Parametric power supply networks (extended abstract)
• Parametric power supply networks
• scientific article; zbMATH DE number 1979534
• Partitioning graphs of supply and demand

Cites work

• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A heuristic method for solving the problem of partitioning graphs with supply and demand
• Approximability of partitioning graphs with supply and demand
• Dealing with 4-variables by resolution: an improved \textsc{MaxSAT} algorithm
• Facility location problems: a parameterized view
• Fundamentals of parameterized complexity
• Improved parameterized algorithms for minimum link-length rectilinear spanning path problem
• Matching and weighted \(P_2\)-packing: algorithms and kernels
• Minimum cost partitions of trees with supply and demand
• Modelling the power supply network -- hardness and approximation
• PARTITIONING TREES OF SUPPLY AND DEMAND
• Parameterized algorithms
• Parameterized complexity of Min-power multicast problems in wireless ad hoc networks
• Parameterized complexity of control and bribery for \(d\)-approval elections
• Parametric power supply networks
• Partitioning graphs of supply and demand
• Randomized parameterized algorithms for P₂-packing and co-path packing problems
• Tree \(t\)-spanners in outerplanar graphs via supply demand partition

Cited in

(9)

• Electrical flows over spanning trees
• Minimum Cost Partitions of Trees with Supply and Demand
• Parameterized algorithms for edge biclique and related problems
• An improved FPT algorithm for almost forest deletion problem
• Parameterized Minimum Cost Partition of a Tree with Supply and Demand
• An improved linear kernel for complementary maximal strip recovery: simpler and smaller
• An approximation algorithm for the \(l\)-pseudoforest deletion problem
• Improved PTAS for the constrained \(k\)-means problem
• Dealing with several parameterized problems by random methods

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q507429)