Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(8)
Combinatorial Optimization
Disjoint Paths
Divide and Conquer
Graph Theory
Polynomial Algorithm
Polynomial Time
Polynomial Time Algorithm
Scientific Research
Subscribe
Academic
Publications
Recognizing a totally odd K4 subdivision, parity 2disjoint rooted paths and a parity cycle through specified elements (extended abstract)
Recognizing a totally odd K4 subdivision, parity 2disjoint rooted paths and a parity cycle through specified elements (extended abstract),Kenichi K
Edit
Recognizing a totally odd K4 subdivision, parity 2disjoint rooted paths and a parity cycle through specified elements (extended abstract)
BibTex

RIS

RefWorks
Download
Kenichi Kawarabayashi
,
Zhentao Lik
,
Bruce Reed
A totally odd K4subdivision is a subdivision of K4 where each subdivided edge has odd length. The recognition of a totally odd K4subdivision plays an important role in both
graph theory
and combinatorial optimization. Sewell and Trotter (53), Zang (63) and Thomassen (60) independently conjectured the existence of a
polynomial time
recognition algorithm. In this paper, we give the first
polynomial time algorithm
for solving this problem. We also study the the parity two disjoint rooted paths problem where we determine if there exists two vertex
disjoint paths
of a specified parity between two pairs of terminals. Using a similar technique, we give an O(E(G)V (G)�(E(G),V (G))) algorithm for the parity two disjoint rooted paths problem on an input graph G, where �(E(G),V (G)) is the inverse of the Ackermann function. We note that this clearly gives an algorithm for the wellknown nonparity version of the two disjoint rooted paths problem (19, 50, 52, 55, 58). We then extend our approach to give a
polynomial time algorithm
which determines, for any fixed k, whether there exists a cycle of a given parity through k independent input edges. This generalizes the nonparity version of the algorithm in (22). Thomassen (61) gave a
polynomial algorithm
for the case k = 2 and hoped to use this algorithm to recog nize a totally odd K4subdivision. Our algorithm runs in O(E(G)V (G)�(E(G),V (G))) for any fixed k. Finally, we give an O(V (G)2 + E(G)�(E(G),V (G)logV (G))) algorithm to de cide whether a graph contains k
disjoint paths
from A to B (with A = B = k) that are not all of the same parity. This answers a conjecture of Thomassen (60). This problem arises from the study of totally oddK4subdivisions ∗T his work was done as a part of an INRIANII collaboration under MOU grant, and partially supported by MEXT Grantin Aid for
Scientific Research
on Priority Areas "New Horizons in Computing" † National Institute of Informatics, 212, Hitotsubashi, Chiyodaku, Tokyo, Japan. ‡Research partly supported by Japan Society for the Promo
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.siam.org
)
References
(52)
Linear time algorithms for NPhard problems restricted to partial ktrees
(
Citations: 214
)
Stefan Arnborg
,
Andrzej Proskurowski
Journal:
Discrete Applied Mathematics  DAM
, vol. 23, no. 1, pp. 1124, 1989
A LinearTime Algorithm for Finding TreeDecompositions of Small Treewidth
(
Citations: 618
)
Hans L. Bodlaender
Journal:
Siam Journal on Computing  SIAMCOMP
, vol. 25, no. 6, pp. 13051317, 1996
Packing NonZero APaths In GroupLabelled Graphs
(
Citations: 21
)
Maria Chudnovsky
,
Jim Geelen
,
Bert Gerards
,
Luis A. Goddyn
,
Michael Lohman
,
Paul D. Seymour
Journal:
Combinatorica
, vol. 26, no. 5, pp. 521532, 2006
Linear Time Solvable Optimization Problems on Graphs of Bounded CliqueWidth
(
Citations: 211
)
Bruno Courcelle
,
Johann A. Makowsky
,
Udi Rotics
Journal:
Theory of Computing Systems / Mathematical Systems Theory  MST
, vol. 33, no. 2, pp. 125150, 2000
Highly Connected Sets and the Excluded Grid Theorem
(
Citations: 64
)
Reinhard Diestel
,
Tommy R. Jensen
,
Konstantin Yu. Gorbunov
,
Carsten Thomassen
Journal:
Journal of Combinatorial Theory  JCT
, vol. 75, no. 1, pp. 6173, 1999