École Polytechnique Fédérale de Lausanne
Infoscience - École polytechnique fédérale de LausanneNot a member yet
191401 research outputs found
Sort by
Autonomous Gossiping: A Self-Organizing Epidemic Algorithm for Selective Information Dissemination in Wireless Mobile Ad-Hoc Networks
No full textLSI
Requirements for Workflow Modeling in P2P-Workflows Derived from Collaboration Establishment
No full textLSI
Object-Oriented Modeling for Hypermedia Systems using the VODAK Modelling Language (VML)
No full textLSI
CrossFlow: Cross-Organizational Workflow Management for Service Outsourcing in Dynamic Virtual Enterprises
No full textLSI
Partitioning cographs into cliques and stable sets
No full textWe consider the problem of partitioning the node set of a graph into p cliques and k stable sets, namely the (p,k)-coloring problem. Results have been obtained for general graphs \cite{hellcomp}, chordal graphs \cite{hellchordal} and cacti for the case where k=p in \cite{tidosplit} where some upper and lower bounds on the optimal value minimizing k are also presented. We focus on cographs and devise some efficient algorithms for solving (p,k)-coloring problems and cocoloring problems in O(n^2+nm) time and O(n^{3/2}) time respectively. We also give an algorithm for finding the maximum induced (p,k)-colorable subgraph. In addition to this, we present characterizations of (2,1)- and (2,2)-colorable cographs by forbidden configurations.ROS