Partitioning graphs of supply and demand

DOI10.1016/j.dam.2008.08.012zbMath1211.05129OpenAlexW2048212722MaRDI QIDQ967306

Takao Nishizeki, Takehiro Ito, Xiao Zhou

Publication date: 28 April 2010

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2008.08.012

zbMATH Keywords

partial \(k\)-treeseries-parallel graphdemand vertexsupply vertexgraph partition problem

Mathematics Subject Classification ID

Applications of graph theory (05C90) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (6)

Parameterized Minimum Cost Partition of a Tree with Supply and Demand ⋮ Minimum cost partitions of trees with supply and demand ⋮ Partition on trees with supply and demand: kernelization and algorithms ⋮ A strongly polynomial time algorithm for the maximum supply rate problem on trees ⋮ Parametric Power Supply Networks ⋮ Parametric power supply networks

Cites Work

• Unnamed Item
• Monadic second-order evaluations on tree-decomposable graphs
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• Easy problems for tree-decomposable graphs
• Linear-time computability of combinatorial problems on series-parallel graphs
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• PARTITIONING TREES OF SUPPLY AND DEMAND

This page was built for publication: Partitioning graphs of supply and demand