Vertex splitting in dags and applications to partial scan designs and lossy circuits

DOI10.1142/S0129054198000301MaRDI QIDQ5248984zbMATH OpenOpenAlexFDO

Authors Doowon Paik, Sudhakar M. Reddy, Sartaj Sahni

Publication date 29 April 2015

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054198000301

zbMATH Keywords

flip-flop selectionlossy circuits and networksNP-hardpartial-scan designspipelined circuitssequential circuits

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Applications of graph theory to circuits and networks (94C15)

Recommendations

• Deleting vertices to bound path length
• On a DAG partitioning problem
• Optimal Reduction of Two-Terminal Directed Acyclic Graphs
• scientific article; zbMATH DE number 3858435
• Min-cut partitioning on underlying tree and graph structures

Cited in

(4)

• Deleting vertices to bound path length
• Splitting plane graphs to outerplanarity
• Splitting plane graphs to outerplanarity
• On the complexity of establishing hereditary graph properties via vertex splitting

This page was built for publication: Vertex splitting in dags and applications to partial scan designs and lossy circuits

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