Philip Klein - bibTex
@InProceedings{MultiwayCut2012,
author = {Mohammadhossein Bateni
and Mohammadtaghi Hajiaghayi and Philip Klein and Claire Mathieu},
title = {A Polynomial-time
Approximation Scheme for Planar Multiway Cut},
booktitle = {Proceedings of the 23rd Annual ACM-SIAM
Symposium on Discrete Algorithms},
year = 2012,
note = {to appear}}
@InProceedings{EfficientSteinerForestPTAS2011,
author = {David Eisenstat and
Philip N. Klein and Claire Mathieu},
title = {An efficient
polynomial-time approximation scheme for Steiner forest in planar
graphs},
booktitle = {Proceedings of the 23nd ACM-SIAM Symposium On
Discrete Algorithms},
year = 2012,
note = {to appear}}
@InProceedings{MSMSflow2011,
author = {Glencora Borradaile and
Philip N. Klein and
Shay Mozes and
Yahav Nussbaum and
Christian Wulff-Nilsen},
title = {Multiple-Source
Multiple-Sink Maximum Flow in Directed Planar
Graphs in Near-Linear Time},
booktitle = {Proceedings of the 52nd Annual IEEE Symposium
on
Foundations of Computer Science},
year = 2011,
note = {to appear}}
@InProceedings{KKS2011,
author = {Ken-ichi
Kawarabayashi and
Philip N. Klein and
Christian Sommer},
title =
{Linear-Space Approximate Distance Oracles for Planar,
Bounded-Genus,
and Minor-Free Graphs},
booktitle = {Proceedings of the 38th International
Colloquium on Automata, Languages and Programming, {ICALP} 2011},
pages = {135-146},
year = 2011}
@InProceedings{KleinM11,
author = {Philip N. Klein and Shay
Mozes},
title = {Multiple-Source
Single-Sink Maximum Flow in Directed Planar Graphs in
$O(\mbox{diameter }n \log n)$ Time},
booktitle = {Proceedings of the 12th Algorithms and Data
Structures Symposium, WADS 2011},
year = 2011,
pages = {571-582}}
@Article{BorradaileKleinMathieu2009,
author = {Glencora Borradaile and
Philip N. Klein and Claire Mathieu},
title = {A polynomial-time
approximation schee for Steiner tree in planar graphs},
journal = {ACM Transactions on
Algorithms},
year = 2009,
volume = 5,
note = {Special Issue on SODA
2007}}
@InProceedings{DemaineHajiaghayiKlein2009,
author = {Erik D. Demaine and
MohammadTaghi Hajiaghayi and Philip Klein},
title = {Node-weighted Steiner
tree and
group Steiner tree in planar graphs},
booktitle = {Proceedings of the 36th International
Colloquium on
Automata, Languages and Programming},
year = 2009}
@Article{BorradaileKlein2009,
author = {Glencora Borradaile
and
Philip N. Klein},
title = {An $O(n \log n)$
algorithm for
maximum st-flow in a directed planar graph},
journal = {Journal of the ACM},
year = 2009,
volume = 56,
number = 2}
@InProceedings{KleinMozesWeimann2009,
author = {Philip N. Klein and Shay
Mozes and Oren Weimann},
title = {Shortest paths in
directed
planar graphs with negative lengths: a linear-space $O(n \log^2
n)$-time algorithm},
booktitle = {Proceedings of the Twentieth Annual ACM-SIAM
Symposium on Discrete Algorithms},
pages = {236-245},
year = 2009}
@Article{KleinTSP2008,
author = {Philip N. Klein},
title = {A linear-time
approximation
scheme for TSP in undirected planar graphs with edge-weights},
journal = {SIAM Journal on
Computing},
year = 2008,
volume = 37,
number = 6,
pages = {1926-1952}}
@InProceedings{BorradaileKlein2008,
author = {Glencora Borradaile and
Philip N. Klein},
title = {The two-edge connectivity
survivable network problem in planar graphs},
booktitle = {Proceedings of the 35th International
Conference on
Automata, Languages, and Programming},
pages = {485-501},
year = 2008}
@InProceedings{BorradaileKleinMathieu2008,
author = {Glencora Borradaile,
Philip
N. Klein, and Claire Mathieu},
title = {A polynomial-time
approximation scheme for Euclidean Steiner forest},
booktitle = {Proceedings of the 49th Annual IEEE Symposium
on
Foundations of Computer Science},
pages = {115-124},
year = 2008}
@InProceedings{KleinTSP2005,
author = {Philip N. Klein},
title = {A linear-time approximation
scheme
for TSP for planar weighted graphs},
booktitle = {Proceedings, 46th IEEE
Symposium on Foundations of Computer Science},
pages = {146-155},
year = 2005
}
@Article{SebKleKim2004,
author = "Thomas Sebastian, Philip N. Klein, and Benjamin Kimia",
title = "Recognition of shapes by editing their shock graphs",
journal = "IEEE Transactions on Pattern Analysis and Machine
Intelligence",
pages="550-571",
volume = "26",
number = 5,
year = "2004",
}
@Article{KleLuNet03,
author = "Klein and Lu and Netzer",
title = "Detecting Race Conditions in Parallel Programs that
Use Semaphores",
journal = "Algorithmica",
pages="321-345",
volume = "35",
year = "2003",
}
@Article{KleinPAMI2003,
author = {T. B. Sebastian and P. N. Klein and B. B. Kimia},
title = {On aligning curves},
journal = {IEEE Transactions on Pattern Analysis and Machine
Intelligence},
year = 2003,
volume = 25,
number = 1,
pages = {116-125}
}
@Article{Sebastian:2002:SBI,
author = "Thomas B. Sebastian and Philip N. Klein and Benjamin
B. Kimia",
title = "Shock-Based Indexing into Large Shape Databases",
journal = "Lecture Notes in Computer Science",
volume = "2352",
pages = "731-746",
year = "2002",
}
@Article{oai:arXiv.org:cs/0208004,
title = "Detecting Race Conditions in Parallel Programs that
Use Semaphores",
author = "Philip N. Klein and Hsueh-I Lu and Rob H. B. Netzer",
month = aug # "~03",
journal = "Algorithmica",
volume = "35",
pages = ":321-345"
year = "2003",
}
@InProceedings{SODA02*820,
author = "Philip N. Klein",
title = "Preprocessing an Undirected Planar Network to Enable
Fast",
pages = "820--827",
booktitle = "Proceedings of the 13th Annual {ACM}-{SIAM} Symposium
On Discrete Mathematics ({SODA}-02)",
month = jan # " ~6--8",
publisher = "ACM Press",
address = "New York",
year = "2002",
}
@InProceedings{SODA01*781,
author = "Philip N. Klein and Thomas B. Sebastian and Benjamin
B. Kimia",
title = "Shape Matching using Edit-distance: An
Implementation",
pages = "781--790",
booktitle = "Proceedings of the Twelfth Annual {ACM}-{SIAM}
Symposium on Discrete Algorithms ({SODA}-01)",
month = jan # " ~7--9",
publisher = "ACM Press",
address = "New York",
year = "2001",
}
@Article{Sebastian:2001:ABR,
author = "Thomas B. Sebastian and Philip N. Klein and Benjamin
B. Kimia",
title = "Alignment-Based Recognition of Shape Outlines",
journal = "Lecture Notes in Computer Science",
volume = "2059",
pages = "606--618",
year = "2001",
}
@InProceedings{ICCV01-VOLI*755,
author = "Thomas Sebastian and Philip Klein and Benjamin Kimia",
title = "Recognition of Shapes by Editing Shock Graphs",
pages = "755--762",
booktitle = "Proceedings of the Eighth International Conference On
Computer Vision ({ICCV}-01)",
month = jul # " ~9--12",
publisher = "IEEE Computer Society",
address = "Los Alamitos, CA",
year = "2001",
}
@inproceedings{352627,
author = {Thomas W. Doeppner and Philip N. Klein and Andrew
Koyfman},
title = {Using router stamping to identify the source of IP
packets},
booktitle = {Proceedings of the 7th ACM conference on Computer and
communications security},
year = {2000},
pages = {184--189},
publisher = {ACM Press},
}
@InProceedings{KleinImageAnalysis2000,
author = {J. Crisco and P. N. Klein and B. B. Kimia and T. B.
Sebastian},
title = {Constructing 2D curve atlases},
booktitle ={Proceedings, IEEE Workshop on
Mathematical Methods in Biomedical Image Analysis},
pages = {70--77},
year = 2000
}
@InProceedings{KleinTirthapuraSODA2000,
author = {P. N. Klein and S. Tirthapura and D. Sharvit and B. B.
Kimia},
title = {A tree-edit-distance algorithm for comparing simple,
closed
shapes},
booktitle ={Proc. ACM-SIAM Symposium on Discrete Algorithms},
pages = {696-704},
year = 2000
}
@inproceedings{338661,
author = {Philip Klein},
title = {Finding the closest lattice vector when it's unusually
close},
booktitle = {Proceedings of the eleventh annual ACM-SIAM symposium
on
Discrete algorithms},
year = {2000},
isbn = {0-89871-453-2},
pages = {937--941},
location = {San Francisco, California, United States},
publisher = {Society for Industrial and Applied Mathematics},
}
@InProceedings{klein99acm,
author = {David R. Karger, Philip N. Klein, Cliff Stein, Mikkel
Thorup,
and Neal E. Young},
title = {Rounding algorithms for a geometric embedding relaxation
of
minimum multiway cut},
booktitle = {Proceedings, ACM Symposium on Theory of Computing},
pages = {668-678},
year = 1999,
}
@InProceedings{klein99number,
author = {Philip Klein and Neal Young},
title = {On the number of iterations for Dantzig-Wolfe
optimization and
packing-covering approximation algorithms},
booktitle = {Proceedings, Integer Programming and Combinatorial
Optimization},
pages = {320-327},
year = 1999,
volume = 1610,
series = {Lecture Notes in Computer Science},
publisher = {Springer-Verlag}
}
@Article{KleSub98,
author = "Klein and Subramanian",
title = "A Fully Dynamic Approximation Scheme for Shortest
Paths in Planar Graphs",
journal = "Algorithmica",
volume = "22",
pages = "235-249",
year = "1998",
}
@InProceedings{KleinSPIE,
author = {S. Tirthapura and D. Sharvit and P. Klein and B. Kimia},
title = {Indexing based on edit-distance matching of shape
graphs},
booktitle ={SPIE International Symposium on Voice, Video, and Data
Communications},
pages = {25--36},
year = 1998
}
@Article{Klein:1998:SEA,
author = "Philip N. Klein and Hsueh-I Lu",
title = "Space-Efficient Approximation Algorithms for {MAXCUT}
and {COLORING} Semidefinite Programs",
journal = "Lecture Notes in Computer Science",
volume = "1533",
pages = "387--396",
year = "1998",
}
@inproceedings{
author = "Philip N. Klein",
title = "Computing the Edit-Distance between Unrooted Ordered
Trees",
journal = "European Symposium on Algorithms",
pages = "91-102",
year = "1998",
}
@inproceedings{
arora98polynomialtime,
author = "Sanjeev Arora and Michelangelo Grigni and David R.
Karger and
Philip N. Klein and Andrzej Woloszyn",
title = "A polynomial-time approximation scheme for weighted
planar
graph TSP",
booktitle = "Symposium on Discrete Algorithms",
pages = "33-41",
year = "1998",
}
@article{
author = {Philip N. Klein, Serge A. Plotkin, Satish Rao,
Éva
Tardos",
title = "Approximation Algorithms for Steiner and Directed
Multicuts",
journal = "Journal of Algorithms",
pages = "241-269",
year = "1997",
}
@Article{HenzingerKRS,
author = {M. R. Henzinger and P. N. Klein and S. Rao and S.
Subramanian},
title = {Faster shortest-path algorithms for planar graphs},
journal = {Journal Comp. Sys. Sci.},
year = 1997,
volume = 55,
number = 1,
pages = {3-23}
}
@article{
author = "Philip N. Klein, Sairam Subramanian",
title = "A Randomized Parallel Algorithm for Single-Source
Shortest
Paths",
journal = "Journal of Algorithms",
year = 1997,
volume = 25,
pages = "205-220",
}
@Article{SICOMP::Klein1996,
title = "Efficient Parallel Algorithms for Chordal Graphs",
author = "Philip N. Klein",
pages = "797--827",
journal = "SIAM Journal on Computing",
month = aug,
year = "1996",
volume = "25",
number = "4",
}
@InProceedings{STOC96*338,
author = "Philip Klein and Hsueh-I. Lu",
title = "Efficient approximation algorithms semidefinite
programs arising from max-cut and coloring",
pages = "338--347",
booktitle = "Proceedings of The Twenty-Eighth Annual {ACM}
Symposium On The Theory Of Computing ({STOC} '96)",
ISBN = "0-89791-785-5",
month = may,
publisher = "ACM Press",
address = "New York, USA",
year = "1996",
}
@InProceedings{ESA::KleinLN1996,
title = "Race-Condition Detection in Parallel Computation with
Semaphores (Extended Abstract)",
author = "Philip N. Klein and Hsueh-I Lu and Robert H. B.
Netzer",
booktitle = "Algorithms---{ESA}~'96, Fourth Annual European
Symposium",
editor = "Josep D{\'\i}az and Maria Serna",
address = "Barcelona, Spain",
month = "25--27~" # sep,
year = "1996",
series = "Lecture Notes in Computer Science",
volume = "1136",
publisher = "Springer",
ISBN = "ISBN 3-540-61680-2",
pages = "445--459",
}
@inProceedings{
title = "Finding Minimum Spanning Forests in Logarithmic Time and
Linear Work Using Random Sampling",
author = "Richard Cole, Philip N. Klein, Robert Endre Tarjan",
journal = "Symposium on Parallel Algorithms and Architecture",
year = "1996",
pages = "243-250",
}
@Article{
author = "David R. Karger, Philip N. Klein, Robert Endre Tarjan",
title = "A Randomized Linear-Time Algorithm to Find Minimum
Spanning
Trees"
journal = "Journal of the ACM",
year = "1995",
volume = "42",
pages = "321-328",
}
@Article{JALGO::KleinR1995,
title = "A Nearly Best-Possible Approximation Algorithm for
Node-Weighted {Steiner} Trees",
author = "Philip Klein and R. Ravi",
pages = "104--115",
journal = "Journal of Algorithms",
year = "1995",
month = jul,
volume = "19",
number = "1",
}
@Article{Klein:1994:DSB,
author = "Philip N. Klein",
title = "A data structure for bicategories, with application to
speeding up an approximation algorithm",
journal = "Information Processing Letters",
volume = "52",
number = "6",
pages = "303--307",
day = "23",
month = dec,
year = "1994",
}
@InProceedings{Klein93,
author = "Philip Klein",
title = "On {G}azit and {M}iller's Parallel Algorithm for
Planar Separators: Achieving Greater Efficiency through
Random Sampling",
booktitle = "Proceedings of the 5th Annual {ACM} Symposium on
Parallel Algorithms and Architectures",
address = "Velen, Germany",
organization = "SIGACT and SIGARCH",
month = jun # " 30--" # jul # " 2,",
year = "1993",
pages = "43--49",
}
@Article{KaoK93,
title={Towards Overcoming the Transitive-Closure Bottleneck:
Efficient
Parallel Algorithms for Planar Digraphs},
author={Ming-Yang Kao and Philip N. Klein},
pages={459--500},
journal=jcss,
year=1993,
month=dec,
volume=47,
number=3,
}
@Article{KNK,
author = {S. Khuller and J. Naor and P. Klein},
title = {The Lattice Structure of Flow in Planar Graphs},
journal = {SIAM J. Discrete Math},
year = 1993,
volume = 6,
number = 3,
pages = {477-490}
}
@InProceedings{Klein:1993:EMN,
author = "Philip Klein and Serge A. Plotkin and Satish Rao",
title = "Excluded minors, network decomposition, and
multicommodity flow",
booktitle ={ACM Symposium on Theory of Computing},
pages = "682--690",
year = 1993,
bibdate = "Wed Feb 20 18:34:01 MST 2002",
bibsource = "http://portal.acm.org/",
}
@Conference{aug:KleinRavi:93,
author = "Philip Klein and R. Ravi",
title = "When Cycles Collapse: {A} General Approximation
Technique for Constraind Two-Connectivity Problems",
booktitle = "Third IPCO Conference",
year = "1993",
editor = "G. Rinaldi and L. Wolsey",
page = "39--55",
}
@Article{KleinR88,
title={An Efficient Parallel Algorithm for Planarity},
author={Philip N. Klein and John H. Reif},
pages={190--246},
journal=jcss,
year=1988,
month=oct,
volume=37,
number=2,
references={}
}