P4-Free Partition and Cover Numbers and Applications

Abstract

P4-free graphs also known as cographs, complement-reducible graphs, or hereditary Dacey graphs have been well studied in graph theory. Motivated by computer science and information theory applications, our work encodes (flat) joint probability distributions and Boolean functions as bipartite graphs and studies bipartite P4-free graphs. For these applications, the graph properties of edge partitioning and covering a bipartite graph using the minimum number of these graphs are particularly relevant.

Document Details

Document Type
Technical Report
Publication Date
Jul 23, 2021
Accession Number
AD1198065

Entities

People

  • Alexander R. Block
  • Hai H. Nguyen
  • Hemanta K. Maji
  • Himanshi Mehta
  • Simina Branzei
  • Tamalika Mukherjee

Organizations

  • Purdue University

Tags

Communities of Interest

  • Cyber
  • Energy and Power Technologies
  • Engineered Resilient Systems

DTIC Thesaurus Topics

  • Algorithms
  • Coding
  • Computational Biology
  • Computational Science
  • Computations
  • Computer Science
  • Cryptography
  • Data Analysis
  • Graph Theory
  • Information Theory
  • Mathematics
  • New York
  • Numbers
  • Probability
  • Probability Distributions
  • Random Variables
  • Theorems
  • Theoretical Computer Science

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.
  • Neurotrauma and Rehabilitation Medicine.
  • Theoretical Analysis.