Displaying similar documents to “On the complexity of covering nodes by K node-disjoint cycles”

Some graphic uses of an even number of odd nodes

Kathie Cameron, Jack Edmonds (1999)

Annales de l'institut Fourier

Similarity:

Vertex-degree parity in large implicit “exchange graphs” implies some EP theorems asserting the existence of a second object without evidently providing a polytime algorithm for finding a second object.

A note to independent sets in scheduling

Jan Černý (1995)

Applications of Mathematics

Similarity:

The paper studies the bus-journey graphs in the case when they are piecewise expanding and contracting (if described by fathers-sons relations starting with the greatest independent set of nodes). This approach can make it possible to solve the minimization problem of the total service time of crews.

Perfectly matchable subgraph problem on a bipartite graph

Firdovsi Sharifov (2010)

RAIRO - Operations Research

Similarity:

We consider the maximum weight perfectly matchable subgraph problem on a bipartite graph with respect to given nonnegative weights of its edges. We show that has a perfect matching if and only if some vector indexed by the nodes in is a base of an extended polymatroid associated with a submodular function defined on the subsets of . The dual problem of the separation problem for the extended polymatroid is transformed to the special maximum flow problem on . In this paper, we give...

On co-bicliques

Denis Cornaz (2007)

RAIRO - Operations Research

Similarity:

A co-biclique of a simple undirected graph is the edge-set of two disjoint complete subgraphs of . (A co-biclique is the complement of a biclique.) A subset is an independent of if there is a co-biclique such that , otherwise is a dependent of . This paper describes the minimal dependents of . (A minimal dependent is a dependent such that any proper subset of is an independent.) It is showed that a minimum-cost dependent set of can be determined in polynomial time for any nonnegative...