On a DAG partitioning problem

DOI10.1007/978-3-642-30541-2_2MaRDI QIDQ2900581zbMATH OpenOpenAlexFDO

Authors Soroush Alamdari, Abbas Mehrabian

Publication date 23 July 2012

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-30541-2_2

zbMATH Keywords

3-SATDAG partitioningfixed parameter tractabilityinapproximabilitypathwidthreduction

Mathematics Subject Classification ID

Distance in graphs (05C12) Directed graphs (digraphs), tournaments (05C20) Signed and weighted graphs (05C22) Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Fixed-parameter algorithms for DAG partitioning
• Parameterized complexity of DAG partitioning
• How to pack directed acyclic graphs into small blocks
• On the hardness of finding near-optimal multicuts in directed acyclic graphs
• How to Pack Directed Acyclic Graphs into Small Blocks

Cited in

(11)

• How to pack directed acyclic graphs into small blocks
• Acyclic digraphs
• Directed acyclic graphs with the unique dipath property
• Deleting vertices to bound path length
• scientific article; zbMATH DE number 841624 (Why is no real title available?)
• Parameterized complexity of DAG partitioning
• On finding optimal polytrees
• Fixed-parameter algorithms for DAG partitioning
• Complexity and approximability of the marking problem
• Vertex splitting in dags and applications to partial scan designs and lossy circuits
• Scheduling analysis and correction for dependent real-time tasks upon heterogeneous multiprocessor architectures

This page was built for publication: On a DAG partitioning problem

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