Edge-disjoint paths in permutation graphs

C. P. Gopalakrishnan; C. Pandu Rangan

Displaying similar documents to “Edge-disjoint paths in permutation graphs”

A linear algorithm for the two paths problem on permutation graphs

C.P. Gopalakrishnan, C. Pandu Rangan (1995)

Discussiones Mathematicae Graph Theory

Similarity:

The 'two paths problem' is stated as follows. Given an undirected graph G = (V,E) and vertices s₁,t₁;s₂,t₂, the problem is to determine whether or not G admits two vertex-disjoint paths P₁ and P₂ connecting s₁ with t₁ and s₂ with t₂ respectively. In this paper we give a linear (O(|V|+ |E|)) algorithm to solve the above problem on a permutation graph.

Graph pattern analysis with PatternGravisto.

Klukas, Christian, Koschützki, Dirk, Schreiber, Falk (2005)

Journal of Graph Algorithms and Applications

Similarity:

An exact performance bound for an $O (m + n)$ time greedy matching procedure.

Shapira, Andrew (1997)

The Electronic Journal of Combinatorics [electronic only]

Similarity:

Combinatorial labelings of graphs.

Hegde, Suresh Manjanath, Shetty, Sudhakar (2006)

Applied Mathematics E-Notes [electronic only]

Similarity:

Listing all plane graphs.

Yamanaka, Katsuhisa, Nakano, Shin-Ichi (2009)

Journal of Graph Algorithms and Applications

Similarity:

A multilevel algorithm for force-directed graph-drawing.

Walshaw, Chris (2003)

Journal of Graph Algorithms and Applications

Similarity:

Theorem proving through depth-first test

Zsolt Tuza (1992)

Acta Universitatis Carolinae. Mathematica et Physica

Similarity:

Edge-Transitive Lexicographic and Cartesian Products

Wilfried Imrich, Ali Iranmanesh, Sandi Klavžar, Abolghasem Soltani (2016)

Discussiones Mathematicae Graph Theory

Similarity:

In this note connected, edge-transitive lexicographic and Cartesian products are characterized. For the lexicographic product G ◦ H of a connected graph G that is not complete by a graph H, we show that it is edge-transitive if and only if G is edge-transitive and H is edgeless. If the first factor of G ∘ H is non-trivial and complete, then G ∘ H is edge-transitive if and only if H is the lexicographic product of a complete graph by an edgeless graph. This fixes an error of Li, Wang,...

Experiments with the fixed-parameter approach for two-layer planarization.

Suderman, Matthew, Whitesides, Sue (2005)

Journal of Graph Algorithms and Applications

Similarity:

A linear algorithm to recognize maximal generalized outerplanar graphs

José Cáceres, Alberto Márquez (1997)

Mathematica Bohemica

Similarity:

In this work, we get a combinatorial characterization for maximal generalized outerplanar graphs (mgo graphs). This result yields a recursive algorithm testing whether a graph is a mgo graph or not.