How to pack directed acyclic graphs into small blocks

DOI10.1016/J.DAM.2020.08.005MaRDI QIDQ2208351zbMATH OpenOpenAlexFDO

Authors Yuichi Asahiro, Tetsuya Furukawa, Keiichi Ikegami, Eiji Miyano, Tsuyoshi Yagita

Publication date 2 November 2020

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

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

zbMATH Keywords

approximabilitydirected acyclic graphgreedy algorithminapproximabilityminimum block transfer problemNP-hardness

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• How to Pack Directed Acyclic Graphs into Small Blocks
• On a DAG partitioning problem
• Fixed-parameter algorithms for DAG partitioning
• scientific article; zbMATH DE number 1974111
• Replica placement on directed acyclic graphs

Cites work

• Algorithms and data structures for external memory
• Clustering without replication in combinatorial circuits
• Disjoint clustering in combinatorial circuits
• How to Pack Directed Acyclic Graphs into Small Blocks
• How to Pack Trees
• scientific article; zbMATH DE number 42110 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1330032 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1947390 (Why is no real title available?)
• scientific article; zbMATH DE number 1746883 (Why is no real title available?)
• scientific article; zbMATH DE number 871936 (Why is no real title available?)
• I/O-efficient point location using persistent B-trees
• Introduction to algorithms.
• On clustering without replication in combinatorial circuits
• On the Complexity of Timetable and Multicommodity Flow Problems
• Optimal Search in Planar Subdivisions
• Succinct and I/O efficient data structures for traversal in trees
• Towards an Architecture-Independent Analysis of Parallel Algorithms

Cited in

(3)

• On a DAG partitioning problem
• How to Pack Directed Acyclic Graphs into Small Blocks
• Fixed-parameter algorithms for DAG partitioning

This page was built for publication: How to pack directed acyclic graphs into small blocks

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