NDLI: Finding short cycles in embedded graph in polynomial time

Please wait, while we are loading the content...

Frontiers of Mathematics in China : Volume 12

Frontiers of Mathematics in China : Volume 11

Frontiers of Mathematics in China : Volume 10

Frontiers of Mathematics in China : Volume 9

Frontiers of Mathematics in China : Volume 8

Frontiers of Mathematics in China : Volume 7

Frontiers of Mathematics in China : Volume 6

Frontiers of Mathematics in China : Volume 5

Frontiers of Mathematics in China : Volume 5, Issue 4, December 2010

Frontiers of Mathematics in China : Volume 5, Issue 3, September 2010

Frontiers of Mathematics in China : Volume 5, Issue 2, June 2010

Finite element method for a nonsmooth elliptic equation

Finite groups with some ss-quasinormal and c-normal subgroups

Second-order differentiability with respect to parameters for differential equations with adaptive delays

On g-s-supplemented subgroups of finite groups

Minimal two-spheres in G(2, 4)

Evolution of noncompact hypersurfaces by mean curvature minus a kind of external force field

Finding short cycles in embedded graph in polynomial time

S-quasinormallity of finite groups

Total versus single point blow-up in a localized heat system

Linear stability of some symplectic matrices

Frontiers of Mathematics in China : Volume 5, Issue 1, January 2010

Frontiers of Mathematics in China : Volume 4

Frontiers of Mathematics in China : Volume 3

Frontiers of Mathematics in China : Volume 2

Frontiers of Mathematics in China : Volume 1

Finding short cycles in embedded graph in polynomial time

Content Provider	Springer Nature Link
Author	Ren, Han Cao, Ni
Copyright Year	2010
Abstract	Let be the set of fundamental cycles of breadth-first-search trees in a graph G, and let be the set of the sums of two cycles in . Then we show the following: (1) contains a shortest Π-twosided cycle in a Π-embedded graph G. This implies the existence of a polynomially bounded algorithm to find a shortest Π-twosided cycle in an embedded graph and thus solves an open problem of Mohar and Thomassen [Graphs on Surfaces, 2001, p. 112]. (2) contains all the possible shortest even cycles in a graph G. Therefore, there are at most polynomially many shortest even cycles in any graph. (3) Let be the set of all the shortest cycles of a graph G. Then is a subset of . Furthermore, many types of shortest cycles are contained in . Infinitely many examples show that there are exponentially many shortest odd cycles, shortest Π-onesided cycles and shortest Π-twosided cycles in some (embedded) graphs.
Starting Page	319
Ending Page	327
Page Count	9
File Format	PDF
ISSN	16733452
Journal	Frontiers of Mathematics in China
Volume Number	5
Issue Number	2
e-ISSN	16733576
Language	English
Publisher	SP Higher Education Press
Publisher Date	2010-01-02
Publisher Institution	Chinese Universities
Publisher Place	Heidelberg
Access Restriction	Subscribed
Subject Keyword	Π-twosided cycle breadth-first-search tree embedded graph Planar graphs; geometric and topological aspects of graph theory Enumeration in graph theory Eulerian and Hamiltonian graphs Mathematics
Content Type	Text
Resource Type	Article
Subject	Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

The cycle’s structure of embedded graphs in surfaces

On Short Noncontractible Cycles in Embedded Graphs

Finding Short Cycles in an Embedded Graph in Polynomial Time

Finding short cycles in an embedded graph in polynomial time 1 (807).

Number of Hamiltonian cycles in planar triangulations

Short cycle structure of graphs on surfaces (1) — the uniqueness theorems

On a Lower Bound for Short Noncontractible Cycles in Embedded Graphs

Finding Cycles with Topological Properties in Embedded Graphs

5-Connected Toroidal Graphs are Hamiltonian-Connected

Finding short cycles in embedded graph in polynomial time

Similar Documents

The cycle’s structure of embedded graphs in surfaces

On Short Noncontractible Cycles in Embedded Graphs

Finding Short Cycles in an Embedded Graph in Polynomial Time

Finding short cycles in an embedded graph in polynomial time 1 (807).

Number of Hamiltonian cycles in planar triangulations

Short cycle structure of graphs on surfaces (1) — the uniqueness theorems

On a Lower Bound for Short Noncontractible Cycles in Embedded Graphs

Finding Cycles with Topological Properties in Embedded Graphs

5-Connected Toroidal Graphs are Hamiltonian-Connected

Finding short cycles in embedded graph in polynomial time