Star Partitions of Perfect Graphs

DOI10.1007/978-3-662-43948-7_15zbMath1409.68148arXiv1402.2589OpenAlexW2145610052MaRDI QIDQ5167740

Laurent Bulteau, Jiehua Chen, Robert Bredereck, Vincent Froese, Rolf Niedermeier, René van Bevern, Gerhard J. Woeginger

Publication date: 1 July 2014

Published in: Journal of Graph Theory, Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1402.2589

zbMATH Keywords

graph algorithmsgraph packinggraph factorsgeneralized matching problem\(P_3\)-partition

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Perfect graphs (05C17)

Related Items (11)

Identification of points using disks ⋮ Network-Based Dissolution ⋮ Induced star partition of graphs ⋮ Complexity and approximation for discriminating and identifying code problems in geometric setups ⋮ Star covers and star partitions of double-split graphs ⋮ An improved approximation algorithm for the minimum 3-path partition problem ⋮ Approximating the directed path partition problem ⋮ Improved approximation algorithms for weighted 2-path partitions ⋮ Discriminating Codes in Geometric Setups ⋮ Partitioning graphs into induced subgraphs ⋮ Network-Based Vertex Dissolution

Cites Work

• Unnamed Item
• The weak 3-flow conjecture and the weak circular flow conjecture
• Combinatorial and computational aspects of graph packing and graph decomposition
• Nowhere-zero 3-flows and modulo \(k\)-orientations
• Interval scheduling and colorful independent sets
• NP-completeness results for some problems on subclasses of bipartite and chordal graphs
• A linear time recognition algorithm for proper interval graphs
• On the complexity of partitioning graphs into connected subgraphs
• Rectilinear planar layouts and bipolar orientations of planar graphs
• General factors of graphs
• Bipartite permutation graphs
• NP-completeness of graph decomposition problems
• \(k\)-path partitions in trees
• Matching and multidimensional matching in chordal and strongly chordal graphs
• On the \(k\)-path partition of graphs.
• Approximation algorithms for the test cover problem
• Algorithmic graph theory and perfect graphs
• Quasi-threshold graphs
• Partition into triangles on bounded degree graphs
• Packing bipartite graphs with covers of complete bipartite graphs
• The path partition problem and related problems in bipartite graphs
• On the Complexity of General Graph Factor Problems
• The LBFS Structure and Recognition of Interval Graphs
• Generalized planar matching
• Interval scheduling: A survey
• A Linear Recognition Algorithm for Cographs
• Planar 3DM is NP-complete
• Linear-time computability of combinatorial problems on series-parallel graphs
• Graph Classes: A Survey
• Network-Based Vertex Dissolution

This page was built for publication: Star Partitions of Perfect Graphs